题目意思是有一些蜥蜴在一个迷宫里面，求这些蜥蜴还有多少是无论如何都逃不出来的。题目只给定一个行数，一个最远能够跳跃的距离，列数是不确定的（题目告知列数小于等于20），但是数据一定会是一个矩阵。每只蜥蜴有一个初始的位置，题目保证这些位置都有一些柱子，每次蜥蜴从一个位置跳到另外一个位置的时候，就会由于反作用力使得一根柱子倒下。很显然，这一题，可以用网络流来求解，那么如何去构图呢？首先我们要确定一个贪心思想，即如果从某一根柱子能够直接跳到迷宫的外面，那么我们就将这个点连接到汇点，而不用将这个点连接到其他的点了。对于哪些不能跳出去但是又有柱子的点，那么我们就去按照跳跃距离搜寻有没有其他的柱子能够去跳跃，如果能够找到的话，那么连接这两点，并且将容量控制为弧尾节点的柱子数，也正是由于一条弧只能够约束一个顶点，所以我们需要进行拆点，点内之间流量为本身柱子数。题目给定的第二个矩阵其实就是用来确定源点的。该题输入要小心，要符合英语语法～～
代码如下：
#include#include #include #include #include #define RE(x) ((x)^1)#define CP(x) ((x)+500)#define INF 0x3fffffffusing namespace std;// 把所有的L点都视作源点，超级源点与该点的容量为1// 并将所有的能够脱离的有柱子的点视作汇点，与超级汇点的容量为弧尾柱子的数目// 将所有的能够相连的柱子都相连，容量为弧尾的柱子数int N, M, MM, dis[1000], head[1000], idx;const int source = 980, sink = 981;char G[25][25], S[25][25];struct Edge{ int v, cap, next;}e[20000];void init(){ idx = -1; memset(head, 0xff, sizeof (head));}inline int to(int x, int y){ return x*M+y;}inline bool out(int x, int y){ int u = x+1, d = N-x, l = y+1, r = M-y; int dist = min(u, min(d, min(l, r))); return dist <= MM;}inline bool judge(int x, int y){ if (x < 0 || x >= N || y < 0 || y >= M) { return false; } else if (!G[x][y]) { return false; } return true;}void insert(int a, int b, int c){ ++idx; e[idx].v = b, e[idx].cap = c; e[idx].next = head[a], head[a] = idx;}void build(int x, int y){ int xx, yy; if (G[x][y]) { insert(to(x, y), CP(to(x,y)), G[x][y]); insert(CP(to(x, y)), to(x,y), G[x][y]); if (out(x, y)) { insert(CP(to(x, y)), sink, INF); insert(sink, CP(to(x, y)), 0); } else { for (int i = -MM; i <= MM; ++i) { for (int j = -(MM-abs(i)); j <= (MM-abs(i)); ++j) { xx = x + i, yy = y + j; if (judge(xx, yy) && !(x == xx && y == yy)) { insert(CP(to(x, y)), to(xx, yy), G[x][y]); insert(to(xx, yy), CP(to(x, y)), 0); } } } } }}bool spfa(int u){ queue q; memset(dis, 0xff, sizeof (dis)); dis[u] = 0; q.push(u); while (!q.empty()) { u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = e[i].next) { if (dis[e[i].v] == -1 && e[i].cap > 0) { dis[e[i].v] = dis[u] + 1; q.push(e[i].v); } } } return dis[sink] != -1;}int dfs(int u, int flow){ if (u == sink) { return flow; } int tf = 0, sf; for (int i = head[u]; i != -1; i = e[i].next) { if (dis[u]+1 == dis[e[i].v] && e[i].cap > 0 && (sf = dfs(e[i].v, min(flow-tf, e[i].cap)))) { e[i].cap -= sf, e[RE(i)].cap += sf; tf += sf; if (tf == flow) { return flow; } } } if (!tf) { dis[u] = -1; } return tf;}int dinic(){ int ans = 0; while (spfa(source)) { ans += dfs(source, INF); } return ans;}int main(){ int T, ca = 0, ans; scanf("%d", &T); while (T--) { init(); ans = 0; scanf("%d %d", &N, &MM); // M为最长的步长 for (int i = 0; i < N; ++i) { scanf("%s", G[i]); } M = strlen(G[0]); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { G[i][j] -= '0'; build(i, j); } } for (int i = 0; i < N; ++i) { scanf("%s", S[i]); for (int j = 0; j < M; ++j) { if (S[i][j] == 'L') { ++ans; insert(source, to(i, j), 1); insert(to(i, j), source, 0); } } } ans -= dinic(); printf("Case #%d: ", ++ca); if (!ans) { puts("no lizard was left behind."); } else if (ans == 1){ printf("%d lizard was left behind.\n", ans); } else { printf("%d lizards were left behind.\n", ans); } } return 0;}