1066: [SCOI2007]蜥蜴
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3525 Solved: 1765
[Submit][Status][Discuss]
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..
........
........
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
Sample Output
1
HINT
100%的数据满足：1<=r, c<=20, 1<=d<=4
Source
<a href="http://www.lydsy.com/JudgeOnline/problemset.php?search=Pku%202711%20Leapin" lizards'="" style="color: blue; text-decoration: none;">Pku 2711 Leapin' Lizards
对于石柱的高度限制，将石柱拆点，连容量为高度的边，原点向蜥蜴连边，能出去的点向汇点连边，跑最大流即为可以跑出去的蜥蜴数目。
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<climits>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define p(a,b) (a-1)*m+b
#define q(a,b) p(a,b)+n*m
#define N 50005
#define M 2000002
#define inf 1<<26
using namespace std;
inline int read()
{int x=0,f=1;char ch;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m,r,s,t,ans;
char mp[101][101];
int ap[101][101];
bool dis(int a,int b,int x,int y)
{return (a-x)*(a-x)+(b-y)*(b-y)<=r*r;}int head[N],pos=-1,cur[N];
struct edge{int to,next,c;}e[M];
void add(int a,int b,int c)
{pos++;e[pos].to=b,e[pos].c=c,e[pos].next=head[a],head[a]=pos;}
void insert(int a,int b,int c){add(a,b,c);add(b,a,0);}queue<int>Q;bool vis[N];int d[N];
bool bfs()
{for(int i=s;i<=t;i++)vis[i]=0,d[i]=-1;vis[s]=1,d[s]=0;Q.push(s);while(!Q.empty()){int u=Q.front();Q.pop();for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(vis[v]||e[i].c<=0)continue;d[v]=d[u]+1;vis[v]=1;Q.push(v);}}return vis[t];
}
int dfs(int u,int a)
{if(u==t||!a)return a;int flow=0,f;for(int &i=cur[u];i!=-1;i=e[i].next){int v=e[i].to;if(d[v]==d[u]+1&&(f=dfs(v,min(e[i].c,a)))>0){flow+=f,a-=f;e[i].c-=f,e[i^1].c+=f;if(!a)break;}}return flow;
}
int dinic()
{int ret=0;while(bfs()){for(int i=s;i<=t;i++)cur[i]=head[i];ret+=dfs(s,inf);}return ret;
}void init(){memset(head,-1,sizeof(head));}bool check(int x,int y)
{if(n-x<r||m-y<r||x<=r||y<=r)return true;return false;
}
int main()
{n=read(),m=read(),r=read();s=0,t=n*m*2+1;init();for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ap[i][j]=mp[i][j]-'0';for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(mp[i][j]=='L'){insert(s,p(i,j),1);ans++;}if(check(i,j))insert(q(i,j),t,inf);if(ap[i][j])insert(p(i,j),q(i,j),ap[i][j]);for(int x=1;x<=n;x++)for(int y=1;y<=m;y++){if(x==i&&y==j)continue;if(dis(i,j,x,y))insert(q(i,j),p(x,y),inf);}}printf("%d\n",ans-dinic());
}