1066: [SCOI2007]蜥蜴
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4298 Solved: 2181
[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..
........
........
Sample Output
1
HINT
100%的数据满足：1<=r, c<=20, 1<=d<=4
Source
题解
每个石柱有次数限制，那么考虑网络流建图。
将石柱拆成两个点，连一条边，流量为石柱的高度，再在互相能到达的石柱之间连边，流量为inf，源点向每个蟋蟀所在的石柱连边，流量为1，能跳出边界的石柱向汇点连边，流量为inf。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=25,inf=0x3f3f3f3f;
int r,c,d,s,t,sz,k,ans,tot;
int id[N][N],head[N*N*2],vis[N*N*2],dis[N*N*2],cur[N*N*2];
struct node{
int p1,p2,x,y,h;
}a[N*N];
struct edge{
int u,v,flow,next;
}e[N*N*400];
int sqr(int x){
return x*x;
}
double dist(node a,node b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
void addedge(int u,int v,int flow){
e[k]=(edge){u,v,flow,head[u]};
head[u]=k++;
e[k]=(edge){v,u,0,head[v]};
head[v]=k++;
}
queue<int>q;
bool bfs(){
for(int i=1;i<=sz;i++){
vis[i]=0;
dis[i]=inf;
}
dis[s]=0;
q.push(s);
vis[s]=1;
int u,v,flow;
while(!q.empty()){
u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=e[i].next){
v=e[i].v,flow=e[i].flow;
if(flow&&dis[u]+1<dis[v]){
dis[v]=dis[u]+1;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
if(dis[t]==inf)return false;
return true;
}
int dfs(int u,int mf){
int v,flow,x,sum=0;
if(u==t||!mf)return mf;
for(int &i=cur[u];i!=-1;i=e[i].next){
v=e[i].v,flow=e[i].flow;
if(flow&&dis[v]==dis[u]+1){
x=dfs(v,min(mf,flow));
e[i].flow-=x;
e[i^1].flow+=x;
sum+=x;
mf-=x;
if(!mf)break;
}
}
if(!sum)dis[u]=0;
return sum;
}
void dinic(){
while(bfs()){
for(int i=1;i<=sz;i++){
cur[i]=head[i];
}
ans+=dfs(s,inf);
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d%d",&r,&c,&d);
s=++sz,t=++sz;
int cnt=0,x;
char ch[N];
for(int i=1;i<=r;i++){
scanf("%s",ch+1);
for(int j=1;j<=c;j++){
x=ch[j]-'0';
if(x){
a[++cnt].p1=++sz,a[cnt].p2=++sz;
a[cnt].x=i,a[cnt].y=j;
addedge(a[cnt].p1,a[cnt].p2,x);
if(i-d<1||i+d>r||j-d<1||j+d>c){
addedge(a[cnt].p2,t,inf);
}
id[i][j]=cnt;
}
}
}
for(int i=1;i<=cnt;i++){
for(int j=i+1;j<=cnt;j++){
if(dist(a[i],a[j])<=d){
addedge(a[i].p2,a[j].p1,inf);
addedge(a[j].p2,a[i].p1,inf);
}
}
}
for(int i=1;i<=r;i++){
scanf("%s",ch+1);
for(int j=1;j<=c;j++){
if(ch[j]=='L'){
addedge(s,a[id[i][j]].p1,1);
tot++;
}
}
}
dinic();
printf("%d
",tot-ans);
return 0;
}