[bzoj]1066: [SCOI2007]蜥蜴

原题链接：蜥蜴

理解很重要，理解很重要，理解很重要！！

分析：

看到这题首先可能会想到搜索：裸图？？
但是很明显搜索肯定会超时
观察题目，发现每根柱子有跳跃次数上限，想到了什么？？
网络流！！
题目中有坑，每根柱子上只能站一只蜥蜴这个条件其实是没用的。
因为蜥蜴不动的话对柱子高度是没有影响的，只要按顺序跳跃就行了。
那么怎么考虑跳跃次数呢？
可以把每个柱子拆成两个点，一个入点一个出点，从入点到出点有单向流量，流量大小为柱子的高度。
从超级源向每一个蜥蜴的初始点的入点连流量为1的边。
每个能跳出去的点向超级汇连流量为无穷大的边。
再把所有柱子向能跳达的柱子连边，流量为无穷大。
这样子网络流模型就出来了，我们只需要从源点开始跑一遍最大流，然后拿蜥蜴的总个数减去最大流就是我们的答案了。

注意！
第一次写的时候不知道写挂什么了，输出答案一直不对，调错调了一个半小时没有结果，然后重写一遍就对了。所以说如果发现查不出错的话一定要果断重构！！

下面是代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf=0x7fffffff;
int rr,cc,dd,g[25][25],d[5000],s=0,t=1000,mark[25][25];
int ver[500000],head[5000],next[500000],edge[500000],tot=1;
queue  q;
void add(int x,int y,int val){
	ver[++tot]=y;edge[tot]=val;next[tot]=head[x];head[x]=tot;
	ver[++tot]=x;edge[tot]=0;next[tot]=head[y];head[y]=tot;
}
bool judge(int x1,int y1,int x2,int y2){
	if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)>dd*dd)return false;
	else if(g[x1][y1]&&g[x2][y2])return true;
}
bool bfs();
int dinic(int x,int flow);
int main()
{
	//freopen("data.in","r",stdin);
	char ch[21];
	int num=0,ans=0,flow,maxflow=0;
	scanf("%d%d%d",&rr,&cc,&dd);
	for(int i=1;i<=rr;i++){
		scanf("%s",ch);
		for(int j=1;j<=cc;j++){
			g[i][j]=ch[j-1]-'0';
			mark[i][j]=++num;
			if(g[i][j])add(mark[i][j],mark[i][j]+400,g[i][j]);
		}
	}
	for(int i=1;i<=rr;i++){
		scanf("%s",ch);
		for(int j=1;j<=cc;j++){
			if(ch[j-1]=='L'){
				add(s,mark[i][j],1);
				ans++;
			}
		}
	}
	for(int i=1;i<=dd;i++){
		for(int j=1;j<=cc;j++){
			add(mark[i][j]+400,t,inf);
			add(mark[rr-i+1][j]+400,t,inf);
		}
	}
	for(int j=1;j<=dd;j++){
		for(int i=dd+1;i<=rr-dd;i++){
			add(mark[i][j]+400,t,inf);
			add(mark[i][cc-j+1]+400,t,inf);
		}
	}

	for(int i=1;i<=rr;i++)
		for(int j=1;j<=cc;j++)
			for(int p=(i-dd<=0)?1:i-dd;p<=min(rr,i+dd);p++)
				for(int q=(j-dd<=0)?1:j-dd;q<=min(cc,j+dd);q++)
					if(judge(i,j,p,q)&&(i!=p||j!=q))
						add(mark[i][j]+400,mark[p][q],inf);
    //cout<<1<