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 }
原文：http://www.cnblogs.com/fightfordream/p/6241298.html