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 1 HINT 100%的数据满足：1<=r, c<=20, 1<=d<=4
此题是网络流的又一个模型，用DINIC求解。 因为每一个柱子被跳了一次都会变短一个长度，这就可以看做是流量。但是这样只是点权，而网络流需要的是边权，怎么办呢？ 我们可以把一个点拆成两个点，可以理解为一个石柱的顶部和底部。链接它们的这条路的权值就是柱子高度。 然后就是常规套路了。建立超级源和超级汇，连接超级源和所有有蜥蜴的柱子，边权为1；链接所有能一步跳出地图的柱子和超级汇，边权为INF；连接所有可以一步到达的柱子（两个点的顶部和底部分别相连），边权为INF。可以理解为只有蜥蜴走的路线才有真实流量，限制了最大流。 ps:DINIC复杂度玄学。。。 代码如下：
#include<cstdio> #include<string> #include<cstring> using namespace std; const int maxn=1005,maxm=160005,inf=1<<30; int n,m,ans,d,S,T,tot,lnk[maxn],son[maxm],nxt[maxm],w[maxm],dep[maxm],cur[maxm],que[maxm]; inline int read(){ int x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x; } int getid(int x,int y,int z) {return (x-1)*m+y+z*n*m;} void add(int x,int y,int z) { son[++tot]=y,w[tot]=z,nxt[tot]=lnk[x],lnk[x]=tot; son[++tot]=x,w[tot]=0,nxt[tot]=lnk[y],lnk[y]=tot; } int bfs(){ memset(dep,0,sizeof(dep)); int head=0,tail=1; que[tail]=S,dep[S]=1; while (head!=tail) { head++; for (int j=lnk[que[head]];j!=-1;j=nxt[j]) if (dep[son[j]]==0&&w[j]>0) dep[son[j]]=dep[que[head]]+1,que[++tail]=son[j]; } return dep[T]; } int dfs(int x,int sum){ if (x==T) return sum; for (int& j=cur[x];j!=-1;j=nxt[j]) if (w[j]>0&&dep[son[j]]==dep[x]+1) { int sum1=dfs(son[j],min(sum,w[j])); if (sum1>0) {w[j]-=sum1,w[j^1]+=sum1; return sum1;} } return 0; } int dinic(){ while (bfs()) { for (int i=1;i<=T;i++) cur[i]=lnk[i]; ans-=dfs(S,inf); } return ans; } int main(){ n=read(),m=read(),d=read(); tot=-1; memset(lnk,255,sizeof(lnk)); memset(nxt,255,sizeof(nxt)); S=2*n*m+1,T=S+1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ char ch=getchar(); while (ch<'0'||ch>'3') ch=getchar(); if (ch>'0') add(getid(i,j,0),getid(i,j,1),ch-48); if (min(min(i,j),min(n-i+1,m-j+1))<=d) add(getid(i,j,1),T,inf); } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { char ch=getchar(); while (ch!='L'&&ch!='.') ch=getchar(); if (ch=='L') {ans++; add(S,getid(i,j,0),1);} } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int i1=1;i1<=n;i1++) for (int j1=1;j1<=m;j1++) if ((i!=i1||j!=j1)&&(i-i1)*(i-i1)+(j-j1)*(j-j1)<=d*d) add(getid(i,j,1),getid(i1,j1,0),inf); printf("%d\n",dinic()); return 0; }