8
27
2013
0

【BZOJ1565】【NOI2009】植物大战僵尸【最大流+拓扑序】

裸的最大权闭合图,但是预处理比较恶心,我WA了好久。首先如果A保护B,那么就连一条A-->B的边,然后对这个图做拓扑序,把环给去掉(拓扑序算法结束后余下的点集便是环集),接下来对于每个换上的点作DFS,把被它保护的点和间接被它保护的点都去掉。然后对于余下的图进行网络流操作,见图如下:

1.如果A保护B则连一条B-->A流量为无穷大的边。

2.如果A的点权>0则连一条S-->A流量为A的点权的边。

3.如果A得点权<0则连一条A-->T流量为A的点权的绝对值的边。

以上操作的要求是AB均为没有被删去的点。然后跑一便最大流,最大流量为maxflow,令tot为所有点权为正的点的点权之和。则答案就是tot-maxflow

 

program p1565;
	const
		maxn=100000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		b:array[0..2000000] of bian;
		p,f,inw,dst:array[0..10000] of longint;
		x:array[1..10000] of longint;
		pd,bo:array[0..100000] of boolean;
		tot,len,i,j,n,m,k,k1,k2:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].f:=k3;
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	function bfs:boolean;
		var
			k1,k2,k3,now,head,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			pd[0]:=true; head:=1; now:=0; x[1]:=0; dst[0]:=0;
			while now<head do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					k1:=b[i].point;
					if (pd[k1]=false) and (b[i].f>0) and (bo[k1]=true)then begin
						pd[k1]:=true;
						dst[k1]:=dst[x[now]]+1;
						if k1=n+1 then exit(true);
						inc(head);
						x[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[n+1]);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=n+1) or (k2=0) then exit(k2);
			now:=p[k1];
			j:=0;
			while now>-1 do begin
				i:=b[now].point;
				if (b[now].f>0) and (dst[k1]=dst[i]-1) and (bo[i]=true)then begin
					k:=change(i,min(b[now].f,k2));
					k2:=k2-k;
					j:=j+k;
					b[now].f:=b[now].f-k;
					inc(b[now xor 1].f,k);
					if k2=0 then break;
				end;
				now:=b[now].next;
			end;
			if j=0 then dst[k1]:=-1;
			exit(j);
		end;
	function dinic:longint;
		var
			num,i:longint;
		begin
			num:=0;
			while bfs=true do begin
				num:=num+change(0,maxn);
			end;
			exit(num);
		end;
	procedure add(k1,k2,k3:longint);
		begin
			inc(inw[k1]);
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	procedure delete(k:longint);
		var
			i,j:longint;
		begin
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if i mod 2=1 then 
					dec(inw[j]);
				i:=b[i].next;
			end;
		end;
	function findmin:longint;
		var
			i,j:longint;
		begin
			for i:=1 to n do
				if (inw[i]=0) and (bo[i]=false) then
					exit(i);
			exit(0);
		end;
	procedure dfs(k:longint);
		var
			i,j:longint;
		begin
			pd[k]:=true;
			bo[k]:=false;
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if (pd[j]=false) and (i mod 2=1) then
					dfs(j);
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m);
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),-1);
		fillchar(dst,sizeof(dst),0);
		fillchar(inw,sizeof(inw),0);
		len:=-1;
		for i:=1 to n*m do begin
			read(f[i],k);
			for j:=1 to k do begin
				read(k1,k2);
				add(k1*m+k2+1,i,maxn);
			end;
		end;
		for i:=0 to n-1 do
			for j:=0 to m-2 do
				add(i*m+j+1,i*m+j+2,maxn);
		n:=n*m;
		fillchar(bo,sizeof(bo),false);
		while true do begin
			k:=findmin;
			if k=0 then break;
			bo[k]:=true;
			delete(k);
		end;
		tot:=0;
		fillchar(pd,sizeof(pd),false);
		for i:=1 to n do
			if (bo[i]=false) and (pd[i]=false) then 
				dfs(i);
		for i:=1 to n do begin
			if bo[i]=false then continue;
			if f[i]>0 then begin
				add(0,i,f[i]);
				tot:=tot+f[i];
			end else if f[i]<0 then
				add(i,n+1,-f[i]);
		end;
		bo[0]:=true; bo[n+1]:=true;
		tot:=tot-dinic;
		if tot<0 then tot:=0;
		writeln(tot);
	end.
Category: 最大流 | Tags: | Read Count: 1610

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com