[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#之虛方法解讀

下一篇：二叉樹的深度