题目：
题目背景
SCOI2007 DAY1 T3
题目描述
在一个 r 行 c 列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。
每行每列中相邻石柱的距离为 1 ，蜥蜴的跳跃距离是 d ，即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为 1 ，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个石柱上。输入格式
输入第一行为三个整数 r，c，d，即地图的规模与最大跳跃距离。
以下 r 行为石竹的初始状态，0 表示没有石柱，1～3 表示石柱的初始高度。以下 r 行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。输出格式
输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。
样例数据 1
输入 []
5 8 2 00000000 02000000 00321100 02000000 00000000 ........ ........ ..LLLL.. ........ ........
输出
1
备注
【数据范围】
100% 的数据满足：1≤r，c≤20，1≤d≤3 。题解：
感觉这题听经典的··拆点的建图方式在很多题中都有用到···而且感觉问”最多可以逃脱多少blabla···“都可以往这道题上想
这里建图引用hzwer的题解，%%%%%
对于每根石柱，采取一分为二的想法，即把一个点分为两个点（可抽象为石柱底部到顶部），其连线容量限制为石柱高度。
超级源与所有有蜥蜴的点相连，容量为1。
超级汇与地图内所有能跳出的点相连，容量为INF。
对于地图内任意两个石柱，如果间距小于d，就将其中一根石柱的顶部与另一根石柱的底部相连，其连线容量为INF。
构图完成，剩下就是跑一遍最大流，然后用蜥蜴数量减去最大流就是最终结果。
（接下来是我自己的话）一定要注意边的数量一定要开够啊！！wa了半天才发现····
代码：
#include#include #include #include #include #include #include #include #include using namespace std;const int N=1005;const int inf=1e+9;int first[N],next[500001],go[500001],rest[500001],tot=1,src,des,lev[N*2],cur[N*2];int map1[25][25],map2[25][25],num[25][25],cnt=0,ans=0,r,c,d;char s[25];void comb(int a,int b,int c){ next[++tot]=first[a],first[a]=tot,go[tot]=b,rest[tot]=c; next[++tot]=first[b],first[b]=tot,go[tot]=a,rest[tot]=0;}bool jud(int a,int b,int x,int y){ if(((a-x)*(a-x)+(b-y)*(b-y))<=d*d) return true; else return false;}void build(){ for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) num[i][j]=++cnt; for(int i=1;i<=r;i++) { scanf("%s",s+1); for(int j=1;j<=c;j++) { map1[i][j]=s[j]-'0'; if(map1[i][j]) comb(num[i][j],num[i][j]+400,map1[i][j]); } } for(int i=1;i<=r;i++) { scanf("%s",s+1); for(int j=1;j<=c;j++) if(s[j]=='L') { comb(src,num[i][j],1); ans++; } } for(int i=1;i<=d;i++) for(int j=1;j<=r;j++) comb(num[j][i]+400,des,inf); for(int i=c-d+1;i<=c;i++) for(int j=1;j<=r;j++) comb(num[j][i]+400,des,inf); for(int i=d+1;i<=c-d;i++) for(int j=1;j<=d;j++) comb(num[j][i]+400,des,inf); for(int i=d+1;i<=c-d;i++) for(int j=r-d+1;j<=r;j++) comb(num[j][i]+400,des,inf); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) for(int k=i-d;k<=i+d;k++) for(int l=j-d;l<=j+d;l++) if(k>=1&&k<=r&&l>=1&&l<=c&&((i!=k)||(j!=l))) if(jud(i,j,k,l)) comb(num[i][j]+400,num[k][l],inf);}inline bool bfs(){ for(int i=src;i<=des;i++) cur[i]=first[i],lev[i]=-1; static int que[N],tail,u,v; que[tail=1]=src; lev[src]=0; for(int head=1;head<=tail;head++) { u=que[head]; for(int e=first[u];e;e=next[e]) { if(lev[v=go[e]]==-1&&rest[e]) { lev[v]=lev[u]+1; que[++tail]=v; if(v==des) return true; } } } return false;}inline int dinic(int u,int flow){ if(u==des) return flow; int res=0,delta,v; for(int &e=cur[u];e;e=next[e]) { if(lev[v=go[e]]>lev[u]&&rest[e]) { delta=dinic(v,min(flow-res,rest[e])); if(delta) { rest[e]-=delta; rest[e^1]+=delta; res+=delta; if(res==flow) break; } } } if(flow!=res) lev[u]=-1; return res;}inline void maxflow(){ while(bfs()) ans-=dinic(src,inf);}int main(){ //freopen("a.in","r",stdin); src=0; des=805; scanf("%d%d%d",&r,&c,&d); build(); maxflow(); cout< <