1066: [SCOI2007]蜥蜴
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2512 Solved: 1238
[Submit][Status][Discuss]
Description
在一个r行c列的网格地图中有一些高度不同的石柱。一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴能够跳到平面距离不超过d的不论什么一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（假设仍然落在地图内部。则到达的石柱高度不变），假设该石柱原来高度为1。则蜥蜴离开后消失。以后其它蜥蜴不能落脚。不论什么时刻不能有两仅仅蜥蜴在同一个石柱上。
Input
输入第一行为三个整数r。c。d，即地图的规模与最大跳跃距离。下面r行为石竹的初始状态，0表示没有石柱，1~3表示石柱的初始高度。下面r行为蜥蜴位置。“L”表示蜥蜴，“.”表示没有蜥蜴。
Output
输出仅一行。包括一个整数。即无法逃离的蜥蜴总数的最小值。
Sample Input
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........
Sample Output
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
题目要求无法逃离的蜥蜴的最小值，即求能够逃离的蜥蜴的最大值。选择使用最大流。当然重点在构图。
对于每个石柱，我们能够拆成两个点。分别为入点和出点。
对于全部石柱。从入点到出点连边，容量为高度。这里等于限制了每个石柱的跳跃次数。
对于最初有蜥蜴的石柱。从源点向这些点的入点连边。容量为1。由于每个石柱仅仅有一个蜥蜴。
对于随意一对能够相互到达的石柱。分别从彼此的出点到入点连边，容量为正无穷。
等于如果能够有尽可能多的蜥蜴跳过。
对于能够跳到边界外的石柱，从出点向汇点连边。容量为正无穷。
原理同上。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define LL long long
#define pa pair<int,int>
#define MAXN 1000
#define MAXM 100000
#define INF 1000000000
#define f1(x,y) ((x-1)*m+y)
#define f2(x,y) ((x-1)*m+y+m*n)
using namespace std;
int cnt=1,ans=0,s,t,n,m,d;
int head[MAXN],cur[MAXN],dis[MAXN],f[25][25];
char ch[25];
struct edge_type
{
int next,to,v;
}e[MAXM];
inline void add_edge(int x,int y,int v)
{
e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt;
e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt;
}
inline bool bfs()
{
queue<int>q;
while (!q.empty()) q.pop();
memset(dis,-1,sizeof(dis));
dis[s]=0;q.push(s);
while (!q.empty())
{
int tmp=q.front();q.pop();
if (tmp==t) return true;
for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)
{
dis[e[i].to]=dis[tmp]+1;
q.push(e[i].to);
}
}
return false;
}
inline int dfs(int x,int f)
{
int tmp,sum=0;
if (x==t) return f;
for(int &i=cur[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].v&&dis[y]==dis[x]+1)
{
tmp=dfs(y,min(f-sum,e[i].v));
e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
if (sum==f) return sum;
}
}
if (!sum) dis[x]=-1;
return sum;
}
inline void dinic()
{
while (bfs())
{
F(i,1,t) cur[i]=head[i];
ans-=dfs(s,INF);
}
}
inline bool excape(int x,int y)
{
return min(min(x,n+1-x),min(y,m+1-y))<=d;
}
inline bool judge(int x1,int y1,int x2,int y2)
{
if (x1==x2&&y1==y2) return false;
return (f[x1][y1]&&f[x2][y2]&&((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))<=(d*d));
}
int main()
{
scanf("%d%d%d",&n,&m,&d);s=2*n*m+1;t=s+1;
F(i,1,n)
{
scanf("%s",ch);
F(j,1,m) f[i][j]=ch[j-1]-'0';
}
F(i,1,n)
{
scanf("%s",ch);
F(j,1,m) if (ch[j-1]=='L'){add_edge(s,f1(i,j),1);ans++;}
}
F(i,1,n) F(j,1,m) if (f[i][j])
{
add_edge(f1(i,j),f2(i,j),f[i][j]);
if (excape(i,j)) add_edge(f2(i,j),t,INF);
}
F(i,1,n) F(j,1,m) F(ti,max(1,i-d),min(n,i+d)) F(tj,max(1,j-d),min(m,j+d))
if (judge(i,j,ti,tj)) add_edge(f2(i,j),f1(ti,tj),INF);
dinic();
printf("%d\n",ans);
}