HDU 2732：Leapin' Lizards（最大流）

http://acm.hdu.edu.cn/showproblem.php?pid=2732

题意：给出两个地图，蜥蜴从一个柱子跳跃到另外一个地方，那么这个柱子就可能会坍塌，第一个地图是柱子可以容忍跳跃多少次（即从它为起点可以跳跃多少次，然后坍塌），第二个地图是蜥蜴的位置。还有一个跳跃距离d，即蜥蜴可以跳跃不超过d的距离（曼哈顿距离），如果跳到地图外面，即蜥蜴逃跑成功，问最终留下的蜥蜴数最少是多少。

思路：我觉得如果不是在做网络流套题应该想不到这是网络流。其实挺简单的建图。首先考虑蜥蜴的位置，和柱子的位置，如果柱子的位置有蜥蜴，那么这个柱子可以容忍的跳跃次数wi要-1，因为这个地方的蜥蜴必须跳走。然后把蜥蜴的位置，柱子的位置，和地图外边的位置存下来，蜥蜴和柱子拆点，形成一个S->lizard1->lizard2->pil1->pil2->out->T这样的网络。

1、如果蜥蜴可以直接跳到地图外，那么可以在lizard2和out之间连一条边，如果柱子可以跳到地图外，就在pil2和out之间连边，权值都为INF。

2、如果柱子之间如果距离在d之间，那么也可以连边，权值为将要跳到的柱子的wi。

3、如果蜥蜴可以跳到柱子，那么可以连边，权值为柱子的wi。

4、S和lizard1连边权值为1。

5、out和T连边权值为INF。

6、蜥蜴拆点权值为1，柱子拆点权值为wi。

这样就做完了。注意输出要仔细。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <string>
  6 #include <cmath>
  7 #include <queue>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 using namespace std;
 12 #define INF 0x3f3f3f3f
 13 #define N 100010
 14 typedef long long LL;
 15 struct Edge {
 16     int v, nxt, cap;
 17     Edge () {}
 18     Edge (int v, int cap, int nxt) : v(v), cap(cap), nxt(nxt) {}
 19 } edge[N];
 20 struct Node {
 21     int x, y;
 22     friend bool operator < (const Node &a, const Node &b) {
 23         return a.x < b.x;
 24     }
 25 } lizard[N], pil[N], out[N];
 26 int head[N], tot, cur[N], gap[N], pre[N], dis[N], w[N], S, T;
 27 
 28 void Add(int u, int v, int cap) {
 29     edge[tot] = Edge(v, cap, head[u]); head[u] = tot++;
 30     edge[tot] = Edge(u, 0, head[v]); head[v] = tot++;
 31 }
 32 
 33 int Cal(Node a, Node b) {
 34     return abs(a.x - b.x) + abs(a.y - b.y);
 35 }
 36 
 37 void BFS() {
 38     memset(dis, -1, sizeof(dis));
 39     memset(gap, 0, sizeof(gap));
 40     queue<int> que; que.push(T);
 41     dis[T] = 0; gap[0]++;
 42     while(!que.empty()) {
 43         int u = que.front(); que.pop();
 44         for(int i = head[u]; ~i; i = edge[i].nxt) {
 45             Edge& e = edge[i];
 46             if(~dis[e.v]) continue;
 47             dis[e.v] = dis[u] + 1;
 48             que.push(e.v);
 49             gap[dis[e.v]]++;
 50         }
 51     }
 52 }
 53 
 54 int ISAP(int n) {
 55     BFS();
 56     memcpy(cur, head, sizeof(cur));
 57     int ans = 0, i, u = pre[S] = S;
 58     while(dis[S] < n) {
 59         if(u == T) {
 60             int flow = INF, index;
 61             for(i = S; i != T; i = edge[cur[i]].v)
 62                 if(edge[cur[i]].cap < flow) flow = edge[cur[i]].cap, index = i;
 63             for(i = S; i != T; i = edge[cur[i]].v)
 64                 edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;
 65             ans += flow; u = index;
 66         }
 67         for(i = cur[u]; ~i; i = edge[i].nxt)
 68             if(dis[edge[i].v] + 1 == dis[u] && edge[i].cap > 0) break;
 69         if(~i) {
 70             pre[edge[i].v] = u; cur[u] = i;
 71             u = edge[i].v;
 72         } else {
 73             if(--gap[dis[u]] == 0) break;
 74             int md = n;
 75             for(int i = head[u]; ~i; i = edge[i].nxt)
 76                 if(dis[edge[i].v] < md && edge[i].cap > 0)
 77                     md = dis[edge[i].v], cur[u] = i;
 78             gap[dis[u] = md + 1]++;
 79             u = pre[u];
 80         }
 81     }
 82     return ans;
 83 }
 84 
 85 int main() {
 86     int t, cas = 0;
 87     cin >> t;
 88     while(t--) {
 89         int n, d, m; char mp[50][50], s[50][50];
 90         scanf("%d%d", &n, &d);
 91         memset(head, -1, sizeof(head)); tot = 0;
 92         int lzcnt = 0, picnt = 0, oucnt = 0;
 93         for(int i = 1; i <= n; i++) scanf("%*c%s", mp[i] + 1);
 94         m = strlen(mp[1] + 1);
 95         for(int i = 1; i <= n; i++) {
 96             scanf("%*c%s", s[i] + 1);
 97             for(int j = 1; j <= m; j++) {
 98                 if(s[i][j] == 'L') {
 99                     lizard[++lzcnt].x = i, lizard[lzcnt].y = j;
100                     if(mp[i][j] - '0' > 0) {
101                         pil[++picnt].x = i, pil[picnt].y = j, w[picnt] = mp[i][j] - '0' - 1; // 如果柱子位置有蜥蜴,那么流量要-1
102                     }
103                 } else if(mp[i][j] != '0') {
104                     pil[++picnt].x = i, pil[picnt].y = j, w[picnt] = mp[i][j] - '0';
105                 }
106             }
107         }
108         for(int i = 1; i <= n; i++) {
109             out[++oucnt].x = i; out[oucnt].y = 0;
110             out[++oucnt].x = i; out[oucnt].y = m + 1;
111         }
112         for(int i = 1; i <= m; i++) {
113             out[++oucnt].x = 0; out[oucnt].y = i;
114             out[++oucnt].x = n + 1; out[oucnt].y = i;
115         }
116         S = 0; T = 2 * lzcnt + 2 * picnt + oucnt + 1;
117         for(int i = 1; i <= lzcnt; i++) Add(S, i, 1), Add(i, i + lzcnt, 1); // 源点和蜥蜴,蜥蜴拆点
118         for(int i = 1; i <= oucnt; i++) Add(2 * lzcnt + 2 * picnt + i, T, INF); // 边界点和汇点
119         for(int i = 1; i <= picnt; i++) Add(2 * lzcnt + i, 2 * lzcnt + picnt + i, w[i]); // 跳跃点拆点
120         for(int i = 1; i <= lzcnt; i++) {
121             for(int j = 1; j <= picnt; j++) {
122                 if(Cal(lizard[i], pil[j]) <= d && Cal(lizard[i], pil[j]) != 0) {
123                     Add(i + lzcnt, j + 2 * lzcnt, w[j]); // 蜥蜴的第二个点和跳跃点第一个点
124                 }
125             }
126             for(int j = 1; j <= oucnt; j++) {
127                 if(Cal(lizard[i], out[j]) <= d) Add(i + lzcnt, j + lzcnt * 2 + picnt * 2, INF);
128             }
129         }
130         for(int i = 1; i <= picnt; i++) {
131             for(int j = i + 1; j <= picnt; j++) {
132                 if(Cal(pil[i], pil[j]) <= d) {
133                     Add(i + 2 * lzcnt + picnt, j + 2 * lzcnt, INF); // 跳跃点
134                     Add(j + 2 * lzcnt + picnt, i + 2 * lzcnt, INF);
135                 }
136             }
137             for(int j = 1; j <= oucnt; j++) {
138                 if(Cal(pil[i], out[j]) <= d) Add(i + lzcnt * 2 + picnt, j + lzcnt * 2 + picnt * 2, INF);
139             }
140         }
141         int ans = lzcnt - ISAP(T + 1);
142         printf("Case #%d: ", ++cas);
143         if(ans < 2) {
144             if(ans <= 0) printf("no lizard was ");
145             else printf("1 lizard was ");
146         } else {
147             printf("%d lizards were ", ans);
148         }
149         puts("left behind.");
150     }
151     return 0;
152 }

#看了一下别人的思路，一开始自己也想的差不多那样，但是硬是调不出来，就用了这么复杂方法，觉得自己没救了，好简单的思路。

S->pil1->pil2->T，如果柱子上有蜥蜴就将这个点和S连，如果在该柱子可以跳出去，那么就将这个点和T相连，然后和能够相连的柱子连边就好了。再写一遍

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <string>
  6 #include <cmath>
  7 #include <queue>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 using namespace std;
 12 #define INF 0x3f3f3f3f
 13 #define N 100010
 14 typedef long long LL;
 15 struct Edge {
 16     int v, nxt, cap;
 17     Edge () {}
 18     Edge (int v, int cap, int nxt) : v(v), cap(cap), nxt(nxt) {}
 19 } edge[N];
 20 struct Node {
 21     int x, y, w, flag;
 22 } pil[N];
 23 int head[N], tot, cur[N], gap[N], pre[N], dis[N], S, T;
 24 
 25 void Add(int u, int v, int cap) {
 26     edge[tot] = Edge(v, cap, head[u]); head[u] = tot++;
 27     edge[tot] = Edge(u, 0, head[v]); head[v] = tot++;
 28 }
 29 
 30 int Cal(Node a, Node b) {
 31     return abs(a.x - b.x) + abs(a.y - b.y);
 32 }
 33 
 34 void BFS() {
 35     memset(dis, -1, sizeof(dis));
 36     memset(gap, 0, sizeof(gap));
 37     queue<int> que; que.push(T);
 38     dis[T] = 0; gap[0]++;
 39     while(!que.empty()) {
 40         int u = que.front(); que.pop();
 41         for(int i = head[u]; ~i; i = edge[i].nxt) {
 42             Edge& e = edge[i];
 43             if(~dis[e.v]) continue;
 44             dis[e.v] = dis[u] + 1;
 45             que.push(e.v);
 46             gap[dis[e.v]]++;
 47         }
 48     }
 49 }
 50 
 51 int ISAP(int n) {
 52     BFS();
 53     memcpy(cur, head, sizeof(cur));
 54     int ans = 0, i, u = pre[S] = S;
 55     while(dis[S] < n) {
 56         if(u == T) {
 57             int flow = INF, index;
 58             for(i = S; i != T; i = edge[cur[i]].v)
 59                 if(edge[cur[i]].cap < flow) flow = edge[cur[i]].cap, index = i;
 60             for(i = S; i != T; i = edge[cur[i]].v)
 61                 edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;
 62             ans += flow; u = index;
 63         }
 64         for(i = cur[u]; ~i; i = edge[i].nxt)
 65             if(dis[edge[i].v] + 1 == dis[u] && edge[i].cap > 0) break;
 66         if(~i) {
 67             pre[edge[i].v] = u; cur[u] = i;
 68             u = edge[i].v;
 69         } else {
 70             if(--gap[dis[u]] == 0) break;
 71             int md = n;
 72             for(int i = head[u]; ~i; i = edge[i].nxt)
 73                 if(dis[edge[i].v] < md && edge[i].cap > 0)
 74                     md = dis[edge[i].v], cur[u] = i;
 75             gap[dis[u] = md + 1]++;
 76             u = pre[u];
 77         }
 78     }
 79     return ans;
 80 }
 81 
 82 int main() {
 83     int t, cas = 0;
 84     cin >> t;
 85     while(t--) {
 86         int n, d, m; char mp[50][50], s[50][50];
 87         scanf("%d%d", &n, &d);
 88         memset(head, -1, sizeof(head)); tot = 0;
 89         int cnt = 0, tol = 0;
 90         for(int i = 1; i <= n; i++) {
 91             scanf("%s", s[i] + 1);
 92             m = strlen(s[i] + 1);
 93             for(int j = 1; j <= m; j++)
 94                 if(s[i][j] != '0') pil[++cnt].x = i, pil[cnt].y = j, pil[cnt].w = s[i][j] - '0';
 95         }
 96         for(int i = 1; i <= n; i++) {
 97             scanf("%s", mp[i] + 1);
 98             for(int j = 1; j <= m; j++) {
 99                 for(int k = 1; k <= cnt; k++) {
100                     if(pil[k].x == i && pil[k].y == j) {
101                         if(mp[i][j] == 'L') pil[k].flag = 1, tol++;
102                         else pil[k].flag = 0;
103                         break;
104                     }
105                 }
106             }
107         }
108         S = 0, T = 2 * cnt + 1;
109         for(int i = 1; i <= cnt; i++) {
110             Add(i, i + cnt, pil[i].w);
111             if(pil[i].flag == 1) Add(S, i, 1);
112             for(int j = i + 1; j <= cnt; j++) {
113                 if(Cal(pil[i], pil[j]) <= d) {
114                     Add(i + cnt, j, INF);
115                     Add(j + cnt, i, INF);
116                 }
117             }
118             if(pil[i].x <= d || pil[i].y <= d || n - pil[i].x < d || m - pil[i].y < d)
119                 Add(i + cnt, T, INF);
120         }
121 
122         int ans = tol - ISAP(T + 1);
123         printf("Case #%d: ", ++cas);
124         if(ans < 2) {
125             if(ans <= 0) printf("no lizard was ");
126             else printf("1 lizard was ");
127         } else {
128             printf("%d lizards were ", ans);
129         }
130         puts("left behind.");
131     }
132     return 0;
133 }