7
31
2013
0

【BZOJ1189】【HNOI2007】紧急疏散evacuate【最大流】

一道网络流的题目。二分时间,然后把每个出口按照时间拆点,每个人向可以到达门的最短时间以后的门节点连一条流量为1的边。源点到所有人连一条流量为1的边,所有门向汇连一条流量为1的边,如果最大流是人的总数则可以逃离,向下二分。



program p1189;
	const
		h:array[1..4] of longint=(0,1,0,-1);
		z:array[1..4] of longint=(1,0,-1,0);	
	type
		bian=record
			point,next,f:longint;
		end;
		arr=array[1..400] of longint;
	var
		y:array[0..21,0..21] of longint;
		x,s,p,dst:array[0..400000] of longint;
		pd:array[1..400000] of boolean;
		b:array[0..2000000] of bian;
		d:array[1..800] of arr;
		maxn,last,mid,ans,l,r,q,k1,k2,k,long,len,tot,n,m,i,j:longint;
		ch:char;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,0);
		end;
	procedure bfs1(k:longint;var d:arr);
		var
			i,j,head,now:longint;
		begin
			fillchar(s,sizeof(s),0);
			fillchar(pd,sizeof(pd),false);
			head:=1; now:=0; s[1]:=x[k]; d[x[k]]:=0; pd[x[k]]:=true;
			while head>now do begin
				inc(now);
				i:=p[s[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) then begin
						inc(head);
						pd[j]:=true;
						s[head]:=j;
						d[j]:=d[s[now]]+1;
					end;
					i:=b[i].next;
				end;
			end;
		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; s[1]:=0; dst[0]:=0;
			while now<head do begin
				inc(now);
				i:=p[s[now]];
				while i>-1 do begin
					k1:=b[i].point;
					if (pd[k1]=false) and (b[i].f>0) then begin
						pd[k1]:=true;
						dst[k1]:=dst[s[now]]+1;
						if k1=last then exit(true);
						inc(head);
						s[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[last]);
		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=last) 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) 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:longint;
		begin
			num:=0;
			while bfs do 
				num:=num+change(0,maxlongint);
			exit(num);
		end;
	function find(t:longint):boolean;
		var
			q,k,k1,k2,i,j:longint;
		begin
			k:=long*t;
			fillchar(p,sizeof(p),-1);
			fillchar(b,sizeof(b),0);
			len:=-1;
			for i:=1 to long do
				for j:=1 to n*m do begin
					if y[(j-1) div m+1,(j-1) mod m+1]=2 then continue;
					for q:=d[i,j] to t do begin
						k1:=q*long-long+i;
						k2:=k+j;
					{	WRITELN(K1,' ',K2,' ',LONG,' ',Q);}
						add(k2,k1,1);
					end;
				end;
			for i:=1 to k do
				add(i,k+n*m+1,1);
			last:=k+n*m+1;
			for i:=k+1 to n*m+k do
				add(0,i,1);
			if dinic=tot then exit(true) else exit(false);
		end;
	begin
		readln(n,m);
		fillchar(y,sizeof(y),0);
		long:=0;
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='.' then y[i,j]:=1
					else if ch='D' then begin
						inc(long);
						x[long]:=i*m-m+j;
						y[i,j]:=2;
					end;
			end;
			readln;
		end;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			for j:=1 to m do 
				for k:=1 to 4 do begin
					k1:=i+h[k];
					k2:=j+z[k];
					if (y[i,j]<>0) and (y[k1,k2]<>0) then begin
						ade(i*m-m+j,k1*m-m+k2,1);
						ade(k1*m-m+k2,i*m-m+j,1);
					end;
				end;
		fillchar(d,sizeof(d),$3f);
		maxn:=d[1,1];
		for i:=1 to long do
			bfs1(i,d[i]);
		l:=0;
		for i:=1 to long do
			for j:=1 to n*m do
				if (l<d[i,j]) and (d[i,j]<>maxn) then l:=d[i,j];
		r:=0;
		for i:=1 to n do
			for j:=1 to m do
				if y[i,j]=1 then inc(r);
		tot:=r; 
		r:=r+l+1;
		l:=1;
		if find(r)=false then begin
			write('impossible');
			exit;
		end;
		while r>l do begin
			mid:=(r+l) div 2;
			if find(mid) then begin
				r:=mid;
				ans:=mid;
			end else
				l:=mid+1;
		end;
		writeln(ans);
	end.
Category: 最大流 | Tags: | Read Count: 1360

登录 *


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