题意
给出$n\times m$的网格，网格上的一些位置上有一只蜥蜴，所有蜥蜴的最大跳跃距离是$d$，如果一只蜥蜴能跳出网格，那么它就安全了，且每个格子有一个最大跳出次数$x$，即如果有$x$只蜥蜴从这个格子跳出，这个格子就再也不能有蜥蜴进来了，问最少有多少只蜥蜴跳不出网格。
思路
设源点为$s$，汇点为$t$，建图如下：
$x=0$的格子为无用格子，全部不用考虑；
对于一个格子$u$，将其拆成两个结点，入点$u$和出点$u‘$；
若一个格子$u$上有蜥蜴，那么连边$(s, u, 1)$；
若格子$u$能承受$x$次跳出，那么连边$(u, u‘, x)$；
若格子$u$能一次跳出网格，那么连边$(u‘, t, inf)$；
对于每对格子$u,v(u\neq v)$，$u,v$的曼哈顿距离$\leq d$，那么连边$(u‘, v, inf),(v‘, u, inf)$。
最大流就是能跳出网格的蜥蜴的最大数量。
代码实现
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <queue> using std::queue; const int INF = 0x3f3f3f3f, N = 2000, M = 200000; int head[N], d[N]; int s, t, tot, maxflow; struct Edge { int to, cap, nex; } edge[M]; queue<int> q; void add(int x, int y, int z) { edge[++tot].to = y, edge[tot].cap = z, edge[tot].nex = head[x], head[x] = tot; edge[++tot].to = x, edge[tot].cap = 0, edge[tot].nex = head[y], head[y] = tot; } bool bfs() { memset(d, 0, sizeof(d)); while (q.size()) q.pop(); q.push(s); d[s] = 1; while (q.size()) { int x = q.front(); q.pop(); for (int i = head[x]; i; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && !d[v]) { q.push(v); d[v] = d[x] + 1; if (v == t) return true; } } } return false; } int dinic(int x, int flow) { if (x == t) return flow; int rest = flow, k; for (int i = head[x]; i && rest; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && d[v] == d[x] + 1) { k = dinic(v, std::min(rest, edge[i].cap)); if (!k) d[v] = 0; edge[i].cap -= k; edge[i^1].cap += k; rest -= k; } } return flow - rest; } void init(int v_num) { tot = 1, maxflow = 0; s = v_num, t = s + 1; memset(head, 0, sizeof(head)); } int main() { int T, cas = 0; scanf("%d", &T); while (T--) { int n, m, dd; char str[25][25]; scanf("%d %d", &n, &dd); for (int i = 0; i < n; i++) { scanf(" %s", str[i]); if (i == 0) { m = strlen(str[0]); init(n * m * 2); } for (int j = 0, u, v; j < m; j++) if (str[i][j] - ‘0‘ > 0) { u = i * m + j; add(u, u + n * m, str[i][j] - ‘0‘); if (i < dd || i + dd >= n || j < dd || j + dd >= m) { add(u + n * m, t, INF); } for (int k = 0; k <= i; k++) for (int p = 0; p < m; p++) { if (k == i && p >= j) break; if (str[k][p] - ‘0‘ > 0) { v = k * m + p; if (abs(i - k) + abs(j - p) <= dd) { add(u + n * m, v, INF); add(v + n * m, u, INF); } } } } } int sum = 0; for (int i = 0; i < n; i++) { scanf(" %s", str[i]); for (int j = 0; j < m; j++) { if (str[i][j] == ‘L‘) { ++sum; add(s, i * m + j, 1); } } } while (bfs()) maxflow += dinic(s, INF); sum -= maxflow; if (sum == 0) printf("Case #%d: no lizard was left behind.\n", ++cas); else if (sum == 1) printf("Case #%d: 1 lizard was left behind.\n", ++cas); else printf("Case #%d: %d lizards were left behind.\n", ++cas, sum); } return 0; }