BZOJ 1066: [SCOI2007]蜥蜴

starli posted @ 2016年2月27日 17:42 in 网络流 , 150 阅读

这种限制节点经过次数的估计就是网络流了

新建源汇s t

把一个点拆成两个,中间连接一条容量为经过次数的边

对于每一个蜥蜴,从s向这个点的入点连边,容量为1,表示有一条蜥蜴。对于每一个点可达的点从出点连边,容量正无穷,能跳出的向t连边,容量正无穷。跑最大流即可

dinic的时候不要忘记重置cur数组,一直死循环…………

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//点ij为2*(c*(i-1)+j)入和2*(c*(i-1)+j)+1出 s=r*c*2+2 t=r*c*2+3
const int N=200010,INF=209999999;
int to[N],from[N],fl[N],tail=1,pre[N],now[N],ans,d[N],vis[N],q[N*2],L,R,cur[N],r,c,di,tmp,g[50][50],xiyi;
inline int o(int i,int j){return 2*(c*(i-1)+j);}
void add(int u,int v,int f){
	to[++tail]=v;pre[tail]=now[u];now[u]=tail;fl[tail]=f;
	to[++tail]=u;pre[tail]=now[v];now[v]=tail;fl[tail]=0;
}
bool bfs(int s,int t){
	memset(vis,0,sizeof(vis));
	L=R=0;q[++R]=s;vis[s]=1;d[s]=0;
	for(int x=q[++L];L<=R;x=q[++L])
		for(int i=now[x];i;i=pre[i]) if(fl[i]>0 && !vis[to[i]]) d[to[i]]=d[x]+1,vis[to[i]]=1,q[++R]=to[i];
	return vis[t];
}
int dfs(int x,int t,int a){
	if(x==t || a==0) return a;
	int flow=0,f;
	for(int &i=cur[x];i;i=pre[i]) if(d[to[i]]==d[x]+1 && (f=dfs(to[i],t,min(a,fl[i])))>0){
		fl[i]-=f;fl[i^1]+=f;flow+=f;a-=f;
		if(a==0) break;
	}
	return flow;
}
int main(){
	//freopen("1066.in","r",stdin);freopen("1066.out","w",stdout);
	scanf("%d%d%d\n",&r,&c,&di);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++) {
			g[i][j]=getchar()-'0';
			if(g[i][j]) add(o(i,j),o(i,j)^1,g[i][j]);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j])
			for(int x=-di;x<=di;x++)
				for(int y=-di;y<=di;y++) if(abs(x)+abs(y)<=di && i+x>0 && i+x<=r && j+y>0 && j+y<=c && g[i+x][j+y] && ((i+x)!=i || (j+y)!=j)) add(o(i,j)^1,o(i+x,j+y),INF);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			tmp=getchar();
			if(tmp=='L') xiyi++,add(2*r*c+2,o(i,j),1);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j] && min(min(r+1-i,i),min(c+1-j,j)) <= di) 	add(o(i,j)+1,2*r*c+3,INF);
	while(bfs(2*r*c+2,2*r*c+3)) {
		for(int i=1;i<=2*r*c+3;i++) cur[i]=now[i];
		ans+=dfs(2*r*c+2,2*r*c+3,INF);
	}
	ans=xiyi-ans;
	printf("%d",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter