HDU-4568 Hunter 状态压缩

题意：给定一个网格图，图中有一些点要求全部走到，问最少的花费是多少，从任意边界进入，任意边界出去，如果不能够全部走到，输出0。

解法：一次spfa从边界上的所有点出发，计算到K个宝藏的最短路，然后计算出任意两个宝藏之间的最短路，最后状态压缩枚举即可。

代码如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;// 记得要带走全部的物品 const int INF = 0x3f3f3f3f; int N, M, K; int mp[205][205]; int idis[15][15]; // 这个15*15的矩阵用来保留宝藏之间的最短路程 int odis[15]; // 从边界到K个位置的最短距离struct Node {int x, y; }p[15];int que[1000005]; int dis[40005]; char vis[40005]; int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};bool legal(int x, int y) {if (x < 0 || x >= N || y < 0 || y >= M) return false;return true; }void spfa(int sta, int num) {int front = 0, tail = 0;memset(dis, 0x3f, sizeof (dis));memset(vis, 0, sizeof (vis));que[tail++] = sta;dis[sta] = 0, vis[sta] = 1;while (front < tail) {int cur = que[front++], nxt;vis[cur] = 0;int x = cur / M, y = cur % M;int xx, yy;for (int k = 0; k < 4; ++k) {xx = x + dir[k][0], yy = y + dir[k][1];nxt = xx * M + yy;if (legal(xx, yy)) {if (dis[nxt] > dis[cur] + mp[xx][yy]) {dis[nxt] = dis[cur] + mp[xx][yy];if (!vis[nxt]) {vis[nxt] = 1;que[tail++] = nxt;}}}}}for (int i = 0; i < K; ++i) {idis[num][i] = dis[p[i].x * M + p[i].y];} }void bspfa() {int front = 0, tail = 0;memset(dis, 0x3f, sizeof (dis));memset(vis, 0, sizeof (vis));for (int i = 0; i < N; ++i) {int k1 = i * M, k2 = i * M + M-1;que[tail++] = k1, que[tail++] = k2;dis[k1] = mp[i][0], dis[k2] = mp[i][M-1]; // 边界点均被初始距离为0加入进来 vis[k1] = vis[k2] = 1;}for (int j = 1; j < M - 1; ++j) {int k1 = j, k2 = (N-1) * M + j;que[tail++] = k1, que[tail++] = k2;dis[k1] = mp[0][j], dis[k2] = mp[N-1][j];vis[k1] = vis[k2] = 1;}while (front < tail) {int cur = que[front++], nxt;vis[cur] = 0;int x = cur / M, y = cur % M;int xx, yy;for (int k = 0; k < 4; ++k) {xx = x + dir[k][0], yy = y + dir[k][1];nxt = xx * M + yy;if (legal(xx, yy)) {if (dis[nxt] > dis[cur] + mp[xx][yy]) {dis[nxt] = dis[cur] + mp[xx][yy];if (!vis[nxt]) {vis[nxt] = 1;que[tail++] = nxt;}}}}}for (int i = 0; i < K; ++i) {odis[i] = dis[p[i].x*M + p[i].y];} }int f[13][1<<13]; // f[i][j]表示状态为j，并且最后走的位置为i的最少开销 int dfs(int sta, int nxt) {if (~f[nxt][sta] && nxt != -1) {return f[nxt][sta];}if (sta == 0) {return f[nxt][sta] = odis[nxt]; // 从nxt开始进入 }int ret = INF;for (int i = 0; i < K; ++i) {if (sta&(1 << i)) {if (nxt != -1)ret = min(ret, dfs(sta^(1 << i), i) + idis[i][nxt]);elseret = min(ret, dfs(sta^(1 << i), i) + odis[i] - mp[p[i].x][p[i].y]);// 走i点走出去的 }}return f[nxt][sta] = ret; }int solve() {memset(f, 0x3f, sizeof (f));int mask = 1 << K;for (int i = 0; i < K; ++i) f[i][1<<i] = odis[i];for (int i = 2; i < mask; ++i) {if (!(i - (i&(-i)))) continue; // 如果只有一位为1for (int j = 0; j < K; ++j) {if (!(i&(1<<j))) continue;for (int k = 0; k < K; ++k) {f[j][i] = min(f[j][i], f[k][i^(1<<j)] + idis[k][j]);}}}int ret = INF;for (int i = 0; i < K; ++i) {ret = min(ret, f[i][mask-1] + odis[i] - mp[p[i].x][p[i].y]);}return ret; }int main() {int T; // freopen("1.in", "r", stdin);scanf("%d", &T);while (T--) {scanf("%d %d", &N, &M);memset(idis, 0x3f, sizeof (idis));memset(odis, 0x3f, sizeof (odis));for (int i = 0; i < N; ++i) {for (int j = 0; j < M; ++j) {scanf("%d", &mp[i][j]);if (mp[i][j] == -1) mp[i][j] = INF;}}scanf("%d", &K);for (int i = 0; i < K; ++i) {scanf("%d %d", &p[i].x, &p[i].y);}for (int i = 0; i < K; ++i) {spfa(p[i].x * M + p[i].y, i);}bspfa();memset(f, 0xff, sizeof (f));int ret = dfs((1<<K)-1, -1);// int ret = solve(); // 也可 if (ret == INF) puts("0");else printf("%d\n", ret); }return 0; }

 

转载于:https://www.cnblogs.com/Lyush/archive/2013/06/07/3123953.html

总结

以上是生活随笔为你收集整理的HDU-4568 Hunter 状态压缩的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。