P2472 [SCOI2007]蜥蜴
题目描述
在一个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
网络最大流：
超级源点和汇点之间用蜥蜴连接
连边：
1、源点连开始的蜥蜴，只有一只，流量为1
2、蜥蜴和能跳过去的（大于1的）格子之间连边
利用公式((x1-x2)(x1-x2)+(y1-y2)(y1-y2))和(r*r)进行比较
3.还有拆点，把点变成边，目的是限制过点的流量
4.边界点到t，流量为inf
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#define maxn 6000
#define N 6000
#define inf 0x3f3f3f3f
using namespace std;
char s[25];
int n,m,S,T,r;
inline int calc(int a,int b) {
return a*(m-1)+b;
}
struct node {
int v,next,cap;
} e[N<<2];
int head[N<<2],dis[N];
int tot=1;
void add(int x,int y,int z) {
e[++tot]=(node) {y,head[x],z};
head[x]=tot;
}
void addedge(int u,int v,int q) {
add(u,v,q);
add(v,u,0);
}
bool bfs() {
memset(dis,-1,sizeof(dis));
dis[S]=0;
queue<int> q;
q.push(S);
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=head[x]; i; i=e[i].next) {
int v=e[i].v;
if(dis[v]==-1&&e[i].cap) {
dis[v]=dis[x]+1;
q.push(v);
}
}
}
return dis[T]!=-1;
}
int dfs(int now,int f) {
if(now==T) return f;
int rest=f;
for(int i=head[now]; i; i=e[i].next) {
int v=e[i].v;
if(e[i].cap&&dis[v]==dis[now]+1&&rest) {
int t=dfs(v,min(rest,e[i].cap));
if(!t) dis[v]=0;
e[i].cap-=t;
e[i^1].cap+=t;
rest-=t;
}
}
return f-rest;
}
int dinic() {
int ans=0;
while(bfs())
ans+=dfs(S,inf);
return ans;
}
int number[20][20];
int map[21][21];
int main() {
/*从s到蜥蜴点
从蜥蜴到 可到蜥蜴
//拆点，容量为个数
从边界蜥蜴到t*/
scanf("%d%d%d",&n,&m,&r);
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
scanf("%1d",&map[i][j]);
int tot=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
number[i][j]=++tot;
S=0;
T=++tot;
int dsr_today_is_angry=0;
//number是拆点的前面，number+410是拆点的后边
for(int i=1; i<=n; ++i) {
scanf("%s",s+1);
for(int j=1; j<=m; ++j)
if(s[j]=='L') dsr_today_is_angry++,addedge(S,number[i][j],1);//s到蜥蜴 流量 1
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
if(map[i][j])
if(i-r<1||i+r>n||j-r<1||j+r>m)
addedge(410+number[i][j],T,inf);//蜥蜴到t 流量inf
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
if(map[i][j])
for(int ii=i-r; ii<=i+r; ++ii)
if(1<=ii&&ii<=n)
for(int jj=j-r; jj<=j+r; ++jj)
if(map[ii][jj])
if(i!=ii||j!=jj)
if(1<=jj&&jj<=m)
if((i-ii)*(i-ii)+(j-jj)*(j-jj)<=r*r)
addedge(number[i][j]+410,number[ii][jj],inf);//蜥蜴到蜥蜴 流量为inf
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(map[i][j]) addedge(number[i][j],number[i][j]+410,map[i][j]);//连起自己，流量为map
printf("%d",dsr_today_is_angry-dinic());
return 0;
}