题目背景
07四川省选
题目描述
在一个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：
1
说明
100%的数据满足：1<=r, c<=20, 1<=d<=4
Solution：
本题最大流基本建模。
把每个点转为$rank$依次为$1$到$r*c$的点，并拆成两个点$i$和$i+400$; 然后当某个柱子$i$有高度时，$i$与$i+400$连容量为高度的边; 当某个有高度的点$i$能出范围时，$i+400$与$t$连容量为$inf$的边; 当某个点为$L$时，$s$与$i$连容量为$1$的边; 最后扫一遍所有的柱子，两两之间能够互达的，$i+400$与$j$连容量为$inf$的边，$j+400$与$i$连容量为$inf$的边。
跑了最大流后，那么答案就是$L$的个数$-$最大流。
代码：
#include<bits/stdc++.h> #define il inline #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; const int N=100005,inf=233333333; int h[N],cnt=1,s,t=2000,ans,dis[N],r,c,d,tot; int ppp[500],qqq[500],ss; char a[25]; struct edge{ int to,net,v; }e[N]; il void add(int u,int v,int w) { e[++cnt].to=v,e[cnt].net=h[u],e[cnt].v=w,h[u]=cnt; e[++cnt].to=u,e[cnt].net=h[v],e[cnt].v=0,h[v]=cnt; } il bool bfs() { queue<int>q; memset(dis,-1,sizeof(dis)); dis[s]=0,q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].net) if(dis[e[i].to]==-1&&e[i].v>0)dis[e[i].to]=dis[u]+1,q.push(e[i].to); } return dis[t]!=-1; } il int dfs(int u,int op) { if(u==t)return op; int flow=0,used=0; for(int i=h[u];i;i=e[i].net) { int v=e[i].to; if(dis[v]==dis[u]+1&&e[i].v>0){ used=dfs(v,min(op,e[i].v)); if(!used)continue; flow+=used,op-=used; e[i].v-=used,e[i^1].v+=used; if(!op)break; } } if(!flow)dis[u]=-1; return flow; } il bool pd(int x,int y){return x*x+y*y<=d*d;} il int change(int x,int y){return (x-1)*c+y;} int main() { cin>>r>>c>>d; For(i,1,r){ scanf("%s",a+1); For(j,1,c) if(a[j]-'0'>0){ int p=change(i,j); add(p,p+405,a[j]-'0'); ppp[++ss]=i,qqq[ss]=j; if(i<=d||i>r-d||j<=d||j>c-d)add(p+405,t,inf); } } For(i,1,r){ scanf("%s",a+1); For(j,1,c) if(a[j]=='L')add(s,change(i,j),1),tot++; } For(i,1,ss) For(j,i+1,ss) if(pd(ppp[i]-ppp[j],qqq[i]-qqq[j])){ int p=change(ppp[i],qqq[i]),q=change(ppp[j],qqq[j]); add(p+405,q,inf);add(q+405,p,inf); } while(bfs())ans+=dfs(s,inf); cout<<tot-ans; return 0; }