7
31
2013
0

【BZOJ1066】【SCOI2007】蜥蜴【最大流】

这道题是很裸的最大流,和【BZOJ1189】紧急疏散很像,不过这道题不用按照时间拆点,需要对于每个柱子拆点,在同一个柱子的两个点间连一条流量为柱子可以通过蜥蜴数的边(即高度),然后对于这张图做最大流即可。

 

program p1066;
	const
		maxn=100000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		p,dst:array[0..40000] of longint;
		w:array[1..50,1..50] of longint;
		x:array[1..400000] of longint;
		pd:array[0..40000] of boolean;
		b:array[0..40000] of bian;
		len,tot,x1,x2,y1,y2,i,j,n,m,d: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;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		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;
					{writeln(k1,' ',b[i].f);
					readln;}
					if (pd[k1]=false) and (b[i].f>0) then begin
						pd[k1]:=true;
						dst[k1]:=dst[x[now]]+1;
						if k1=n then exit(true);
						inc(head);
						x[head]:=k1;
					end;
					i:=b[i].next;
				end;
			end;	
			exit(pd[n]);
		end;
	function change(k1,k2:longint):longint;
		var
			now,i,j,k:longint;
		begin
			if (k1=n) 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=true do
				num:=num+change(0,maxn);
			exit(num);
		end;
	begin
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		readln(n,m,d);
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				w[i,j]:=ord(ch)-ord('0');
				if (i<=d) or (j<=d) or (i>=n-d+1) or (j>=m-d+1) then add(i*m-m+j+n*m,n*m*2+1,maxn);
			end;
			readln;
		end;
		for x1:=1 to n do 
			for y1:=1 to m do
				for x2:=1 to n do
					for y2:=1 to m do
						if ((x1<>x2) or (y1<>y2)) and (sqrt(sqr(x1-x2)+sqr(y1-y2))<=d) then 
							add(x1*m-m+y1+n*m,x2*m-m+y2,maxn);
		tot:=0;
		for i:=1 to n do begin
			for j:=1 to m do begin
				read(ch);
				if ch='L' then begin
					dec(w[i,j]);
					add(0,i*m-m+j+n*m,1);
					inc(tot);
				end;
				add(i*m-m+j,i*m-m+j+n*m,w[i,j]);
			end;
			readln;
		end;
		n:=n*m*2+1;
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags: | Read Count: 1005

登录 *


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