题意：在一个迷宫里面有一些蜥蜴，这个迷宫有一些柱子组成的，并且这些柱子都有一个耐久值，每当一只蜥蜴跳过耐久值就会减一，当耐久值为0的时候这个柱子就不能使用了，每个蜥蜴都有一个最大跳跃值d，现在想知道有多少蜥蜴不能离开迷宫（跳出迷宫就可以离开了。）
输入描述：输入矩阵的行M和跳跃值D，接着输入两个矩阵（列数自己求），第一个矩阵是每个柱子的耐久值，下面一个矩阵有'L'的表示这个柱子上有一只蜥蜴。
分析：题目明白还是比较容易的，矩阵的点数是20*20，也就400个点，对每个有耐久值的柱子进行拆点，然后连接两个柱子（判断是否在跳跃范围内）,源点和有蜥蜴的柱子相连，汇点和所有能一下跳出来的柱子相连。注意输出的时候单词的复数单数。
下面是AC代码。
=================================================================================================================================
#include<stdio.h> #include< string.h> #include<queue> #include<algorithm> using namespace std; const int MAXN = 1005; const int oo = 1e9+ 7; struct point { int x, y, flow; bool Lizards; }p[MAXN]; struct Edge{ int v, flow, next;}edge[MAXN*MAXN]; int Head[MAXN], cnt, Layer[MAXN]; void InIt() { cnt = 0; memset(Head, - 1, sizeof(Head)); } bool canLine(point a, point b, int d) { /// 判断能否从a点跳到b点 int len = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); if(d*d >= len) return true; else return false; } void AddEdge( int u, int v, int flow) { edge[cnt].v = v; edge[cnt].flow = flow; edge[cnt].next = Head[u]; Head[u] = cnt++; swap(u, v); edge[cnt].v = v; edge[cnt].flow = 0; edge[cnt].next = Head[u]; Head[u] = cnt++; } bool BFS( int start, int End) { memset(Layer, 0, sizeof(Layer)); queue< int> Q; Q.push(start); Layer[start] = 1; while(Q.size()) { int u = Q.front();Q.pop(); if(u == End) return true; for( int j=Head[u]; j!=- 1; j=edge[j].next) { int v = edge[j].v; if(!Layer[v] && edge[j].flow) { Layer[v] = Layer[u] + 1; Q.push(v); } } } return false; } int DFS( int u, int MaxFlow, int End) { if(u == End) return MaxFlow; int uflow = 0; for( int j=Head[u]; j!=- 1; j=edge[j].next) { int v = edge[j].v; if(Layer[v]- 1==Layer[u] && edge[j].flow) { int flow = min(MaxFlow-uflow, edge[j].flow); flow = DFS(v, flow, End); edge[j].flow -= flow; edge[j^ 1].flow += flow; uflow += flow; if(uflow == MaxFlow) break; } } if(uflow == 0) Layer[u] = 0; return uflow; } int Dinic( int start, int End) { int MaxFlow = 0; while( BFS(start, End) == true ) MaxFlow += DFS(start, oo, End); return MaxFlow; } int main() { int T, t= 1; scanf( " %d ", &T); while(T--) { int i, j, N, M, d, k= 0, sum= 0; char s[MAXN]; InIt(); scanf( " %d%d ", &M, &d); for(i= 0; i<M; i++) { scanf( " %s ", s); N = strlen(s); for(j= 0; s[j]; j++) { k++; p[k].x = i; p[k].y = j; p[k].flow = s[j]- ' 0 '; } } for(i=k= 0; i<M; i++) { scanf( " %s ", s); for(j= 0; s[j]; j++) { k++; if(s[j] == ' L ') p[k].Lizards = true; else p[k].Lizards = false; } } int start = k* 2+ 1, End = start+ 1; for(i= 1; i<=k; i++) { if( p[i].flow > 0) { AddEdge(i, i+k, p[i].flow); if(p[i].x-d< 0 || p[i].x+d>=M || p[i].y-d< 0 || p[i].y+d>=N) { /// 能从这点跳出去,与汇点相连 AddEdge(i+k, End, oo); } if(p[i].Lizards) { /// 如果这点是一个蜥蜴,与源点相连，流量是1 AddEdge(start, i, 1); sum++; } for(j= 1; j<=k; j++) { if(i == j) continue; /// 如果能从i跳到j那么让他们相连，注意是拆点i与j相连 if(p[j].flow && canLine(p[i], p[j], d)) AddEdge(i+k, j, oo); } } } int Flow = Dinic(start, End); Flow = sum - Flow; /// 要求逃不出来的 if(Flow == 0) printf( " Case #%d: no lizard was left behind.\n ", t++); else if(Flow == 1) printf( " Case #%d: 1 lizard was left behind.\n ", t++); else printf( " Case #%d: %d lizards were left behind.\n ", t++, Flow); } return 0;
}