【SCOI2007】蜥蜴
Description
在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。Input
输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。 Output 输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。Sample Input
5 8 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........ Sample Output 1HINT
100%的数据满足：1<=r, c<=20, 1<=d<=4
标签：网络流
简单的拆点建模题。
从源点向每个有蜥蜴的点连容量为1的边，从每个能跳出去的点向汇点连容量为INF的边。对于石笋高度，把每个点拆成两个点，它们间的边容量为石笋高度，若位置(i, j)可跳到(p, q)，则从(i, j)的第二个点向(p, q)的第一个点连容量为INF的边。最后跑最大流即可。 点数少，都懒得用边表了，直接用邻接矩阵......附上AC代码：
#include#include #include #include #define MAX_N 20#define INF 2147483647using namespace std;int n, m, r, s, t, cnt, tot, id[MAX_N+5][MAX_N+5], map[MAX_N*MAX_N*2+5][MAX_N*MAX_N*2+5];char a[MAX_N+5][MAX_N+5], b[MAX_N+5][MAX_N+5];void build(int x, int y) { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if ((i != x || j != y) && (a[i][j] != '0') && r*r >= (x-i)*(x-i)+(y-j)*(y-j)) map[id[x][y]+1][id[i][j]] = INF;}int d[MAX_N*MAX_N*2+5];bool BFS() { queue que; memset(d, -1, sizeof(d)); d[s] = 0, que.push(s); while (!que.empty()) { int u = que.front(); que.pop(); for (int v = 0; v <= cnt; v++) { if (d[v] != -1 || !map[u][v]) continue; d[v] = d[u]+1, que.push(v); } } return d[t] != -1;}int DFS(int u, int flow) { if (u == t) return flow; int ret = 0; for (int v = 0; v <= cnt; v++) { if (d[v] != d[u]+1 || !map[u][v]) continue; int tmp = DFS(v, min(flow, map[u][v])); map[u][v] -= tmp, map[v][u] += tmp, flow -= tmp, ret += tmp; if (!flow) break; } if (!ret) d[u] = -1; return ret;}int Dinic() { int ret = 0; while (BFS()) ret += DFS(s, INF); return ret;}int main() { scanf("%d%d%d", &n, &m, &r); for (int i = 1; i <= n; i++) { scanf("%s", a[i]+1); for (int j = 1; j <= m; j++) { if (a[i][j] == '0') continue; id[i][j] = cnt+1, map[cnt+1][cnt+2] = a[i][j]-'0', cnt += 2; } } s = 0, t = ++cnt; for (int i = 1; i <= n; i++) { scanf("%s", b[i]+1); for (int j = 1; j <= m; j++) { if (b[i][j] == 'L') tot++, map[s][id[i][j]] = 1; if (i-r < 1 || i+r > n || j-r < 1 || j+r > m) map[id[i][j]+1][t] = INF; if (a[i][j] != '0') build(i, j); } } printf("%d", tot-Dinic()); return 0;}