[SCOI2007]蜥蜴_牛客博客

题目背景
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 复制

说明/提示
100%的数据满足：1<=r, c<=20, 1<=d<=4

做网络流做得比较多的人应该一下子就能看出这是一个最大流。

考虑建图：网络流的重点就是建图，已经最大流的含义，建图的意义。

建立超级源点S，以及超级汇点T。

最大流的含义：让能跑出去的蜥蜴最多，就是最大流。
对于蜥蜴所在点，我们可以让S连向蜥蜴所在点。
对于每次离开，石柱高度减一，相当于就是限制了每个石柱的流量，所以我们拆点限流即可。
对于石柱之间的跳跃：我们枚举当前石柱能到达的点即可，若能到达就连流量inf的边。
对于每个石柱，如果能跳出去，我们就连向T，流量为inf。

最后跑一次最大流即可，答案就是蜥蜴总数减去最大流。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e5+10;
int n,m,d,h[N],s,t,base,res;
int head[N],nex[M],to[M],w[M],tot=1;
char g[25][25];
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
inline int get(int x1,int y1,int x2,int y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
inline int id(int x,int y){
	return m*(x-1)+y;
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(s);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!h[to[i]]&&w[i]){
				q.push(to[i]);	h[to[i]]=h[u]+1;
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(h[to[i]]==h[x]+1&&w[i]){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
signed main(){
	cin>>n>>m>>d;	s=0;	t=n*m*2+1;	base=n*m;
	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	cin>>g[i][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;	cin>>x;	if(x=='.')	continue;	res++;
			add(s,id(i,j),1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!(g[i][j]-'0'))	continue;
			add(id(i,j),id(i,j)+base,g[i][j]-'0');
			if(i-d<1||i+d>n||j-d<1||j+d>m)	add(id(i,j)+base,t,inf);
			for(int k=1;k<=n;k++){
				for(int s=1;s<=m;s++){
					if(k==i&&j==s||!(g[i][j]-'0'))	continue;
					if(d*d>=get(i,j,k,s))	add(id(i,j)+base,id(k,s),inf);
				}
			}
		}
	}
	cout<<res-dinic()<<endl;
	return 0;
}