[HDU4862]Jump

2019-11-08 19:54:18

字体：大中小

来源：转载

供稿：网友

题目链接：HDU4862

题目大意 在一个N×M $N /times M$ 的棋盘上，每个格子有权值，有不超过 K $K$ 次游戏机会，要求经过全部格子恰好一次。每一次游戏为一系列连续跳跃，以任意点为开始点(未曾到过)，每次跳跃向正右方或正下方跳(可以跳到很远，落地格子不曾到过)，能量花费为|x1−x2|+|y1−y2|−1 $|x1-x2|+|y1-y2|-1$ 。若一次跳跃的起点和终点权值一样，则得到该点数值的能量。起始能量为0 $0$ ，问最终能量最大为多少？

分析 1. 把每次游戏视为图上一个环，即结束点连回开始点，则变成了一个最小K $K$ 环覆盖的问题。 2. 把每个格子拆成两个点，分别在A $A$ 部和B $B$ 部，A $A$ 部点向可达的B $B$ 部点连边，容量为1，费用为能量花费减去所得能量，表示可以跳跃一次。 3. 新建两个点P1 $P1$ ，P2 $P2$ ，容量为K $K$ ，费用为0 $0$ ；A $A$ 部点经过P1 $P1$ ，P2 $P2$ 向其左上方，包括自己的B $B$ 部点连边，费用为0 $0$ ，容量为1 $1$ ；表示从一次游戏的结束点连回起点，且游戏不超过K $K$ 次。 4. 新建S $S$ ，T $T$ ；S $S$ 向A $A$ 部点连边，费用为0 $0$ ，容量为1 $1$ ；B $B$ 部点向T $T$ 连边，费用为0 $0$ ，容量为1 $1$ 。 5. 打模板。 ps. 其实有比较优的建图方法，但我觉得还是这种稍微好理解一点。

上代码

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int P = 15;const int N = 1e2 + 10;const int M = 2e4 + 10;const int INF = 0x3f3f3f3f;int n, m, q;int S, T, P1, P2;int plat[P][P];//取编号的方法之一，个人觉得这样调试起来更友善#define id(x, y, z) ((z) * n * m + (x - 1) * m + (y))int len, head[N << 1];struct nodeLib { int to, next, flow, cost; inline void add(int a, int b, int c, int d) { to = b, flow = c, cost = d; next = head[a], head[a] = len++; }} lib[M << 1];inline void pathLink(int a, int b, int c, int d) { lib[len].add(a, b, c, d), lib[len].add(b, a, 0, -d);}void init() { len = 2; memset(head, 0, sizeof(head)); scanf("%d %d %d", &n, &m, &q); S = id(n, m + 1, 1), T = id(n, m + 2, 1); P1 = id(n, m + 3, 1), P2 = id(n, m + 4, 1); pathLink(P1, P2, q, 0); char ss[P]; //如上述建图 for (int i = 1; i <= n; i++) { scanf("%s", ss + 1); for (int j = 1; j <= m; j++) { plat[i][j] = ss[j] - '0'; pathLink(S, id(i, j, 0), 1, 0); pathLink(id(i, j, 1), T, 1, 0); pathLink(id(i, j, 0), P1, 1, 0); pathLink(P2, id(i, j, 1), 1, 0); } } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int cost = 0; for (int k = i + 1; k <= n; k++) { cost = k - i - 1; cost -= (plat[i][j] == plat[k][j]) ? plat[i][j] : 0; pathLink(id(i, j, 0), id(k ,j, 1), 1, cost); } for (int k = j + 1; k <= m; k++) { cost = k - j - 1; cost -= (plat[i][j] == plat[i][k]) ? plat[i][j] : 0; pathLink(id(i, j, 0), id(i, k, 1), 1, cost); } }}//模板queue <int> Q;bool inQ[N << 1];int dist[N << 1], PReE[N << 1], preV[N << 1];bool SPFA() { memset(dist, 0x3f, sizeof(dist)); dist[S] = 0, Q.push(S), inQ[S] = true; while (!Q.empty()) { int tmp = Q.front(); Q.pop(), inQ[tmp] = false; for (int p = head[tmp]; p; p = lib[p].next) { int to = lib[p].to; if (dist[to] > dist[tmp] + lib[p].cost && lib[p].flow) { dist[to] = dist[tmp] + lib[p].cost; preE[to] = p, preV[to] = tmp; if (!inQ[to]) Q.push(to), inQ[to] = true; } } } return dist[T] < INF;}int figure() { if (q < min(n, m)) return -1; //因为在这里就已经判好了 int ans = 0, totf = 0; while (SPFA()) { int maxf = INF; for (int p = T; p != S; p = preV[p]) maxf = min(maxf, lib[preE[p]].flow); for (int p = T; p != S; p = preV[p]) lib[preE[p]].flow -= maxf, lib[preE[p] ^ 1].flow += maxf; totf += maxf, ans -= dist[T] * maxf; } return (totf == n * m) ? ans : -1; //其实这个判断是多余的}int main() { int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { init(); printf("Case %d : %d/n", i, figure()); } return 0;}

以上

上一篇：C#之虚方法解读

下一篇：二叉树的深度