在一个 \(r\times c\) 的网格地图中有一些石柱，一些石柱上站着一些蜥蜴。 每行每列中相邻石柱的距离为 \(1\) ，蜥蜴的跳跃距离是 \(d\) ，即蜥蜴可以跳到平面距离不超过 \(d\) 的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 \(1\) （如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为 \(1\) ，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。求最少有多少条蜥蜴无法逃离。
\(r,\ c\leq20, 1\leq d\leq4\)
网络流，最大流
将每个石柱拆为出点和入点，边权为石柱高度。若两个石柱 \(a,\ b\) 能够抵达，那么由 \(a\) 的出点连向 \(b\) 的入点，边权 \(\inf\) 。若石柱 \(a\) 可以跳出网格，那么不必从 \(a\) 向其他石柱连边，直接向虚拟汇点连一条 \(\inf\) 的边。由虚拟源点向所有有蜥蜴的石柱连一条边权为 \(1\) 的边。然后就可以愉悦地跑最大流辣
时间复杂度 \(O(\) 雾，反正 \(EK\) 跑不满 \()\)
代码
#includeusing namespace std;const int maxn = 1010, maxm = 5e5 + 10, maxt = 25, inf = 1 << 30;int n, s, t, R, C, D, h[maxn], q[maxn], f[maxn], pre[maxn], mp[maxt][maxt];struct node { int x, y, sz, flg;} a[maxt][maxt];struct edges { int nxt, to, w; edges(int x = 0, int y = 0, int z = 0) : nxt(x), to(y), w(z) {}} e[maxm];void addline(int u, int v, int w) { static int cnt = 1; e[++cnt] = edges(h[u], v, w), h[u] = cnt; e[++cnt] = edges(h[v], u, 0), h[v] = cnt;}int bfs() { memset(f, 0, sizeof f); int l = 1, r = 1; q[1] = s, f[s] = inf; while (l <= r) { int u = q[l++]; for (int i = h[u]; i; i = e[i].nxt) { int v = e[i].to; if (!f[v] && e[i].w) { q[++r] = v, pre[v] = i; f[v] = min(f[u], e[i].w); if (v == t) break; } } } return f[t];}int EK() { int res = 0, tmp; while ((tmp = bfs())) { res += tmp; for (int u = t; u != s; u = e[pre[u] ^ 1].to) { e[pre[u]].w -= tmp, e[pre[u] ^ 1].w += tmp; } } return res;}int main() { char str[maxt]; int R, C, D, tot = 0; scanf("%d %d %d", &R, &C, &D); for (int i = 1; i <= R; i++) { scanf("%s", str + 1); for (int j = 1; j <= C; j++) { a[i][j].sz = str[j] ^ 48; mp[i][j] = ((i - 1) * C + j) << 1; } } for (int i = 1; i <= R; i++) { scanf("%s", str + 1); for (int j = 1; j <= C; j++) { if (str[j] == 'L') { a[i][j].flg = 1, tot++; } } } n = mp[R][C] + 3; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { if (!a[i][j].sz) continue; if (a[i][j].flg) { addline(n - 1, mp[i][j], 1); } if (i <= D || j <= D || R - i < D || C - j < D) { addline(mp[i][j] | 1, n, inf); } addline(mp[i][j], mp[i][j] | 1, a[i][j].sz); } } for (int i = D + 1; i <= R - D; i++) { for (int j = D + 1; j <= C - D; j++) { if (!a[i][j].sz) continue; for (int x = i - D; x <= i + D; x++) { for (int y = j - D; y <= j + D; y++) { if (!a[x][y].sz || abs(i - x) + abs(j - y) > D || (i == x && j == y)) continue; addline(mp[i][j] | 1, mp[x][y], inf); } } } } s = n - 1, t = n; printf("%d", tot - EK()); return 0;}