9
20
2013
0

【BZOJ2150】部落战争【网络流】

由于只能向下走,这样路线就不可能达成一个环,而且又鉴于每个点只能到达一遍,每一次的代价只存在于重设出发点,于是很容易的就想到了最小路径覆盖,赤果果的网络流。把每个节点拆成两个,i入和i出。如果i可以到达j,那么就连一条i出到j入的边,再由源向每一个出连一条边,由入向汇连一条边。上述边的流量都为1。答案就是总的点数减最大流。当然这道题也可以用匈牙利算法做。

program p03;
    type
        bian=record
            next,point,f:longint;
        end;
    var
        b:array[0..5000000] of bian;
        p,dst,s:array[0..500000] of longint;
        pd:array[0..500000] of boolean;
        bo:array[1..600,1..600] of boolean;
        tot,len,i,j,n,m,r,c:longint;
        ch:char;
    procedure getchar(var ch:char);
        begin
            read(ch);
            while (ch<>'.') and (ch<>'x')do
                read(ch);
        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
            i,j,k,num:longint;
        begin
            if (k1=n*m*2+1) or (k2=0) then exit(k2);
            num:=0;
            i:=p[k1];
            while i<>-1 do begin
                j:=b[i].point;
                if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
                    k:=change(j,min(k2,b[i].f));
                    k2:=k2-k; num:=num+k;
                    dec(b[i].f,k); inc(b[i xor 1].f,k);
                    if k2=0 then break;
                end;
                i:=b[i].next;
            end;
            if num=0 then dst[k1]:=-1;
            exit(num);
        end;
    function bfs:boolean;
        var
            i,j,head,now:longint;
        begin
            fillchar(dst,sizeof(dst),-1);
            fillchar(pd,sizeof(pd),false);
            head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
            while head>now do begin
                inc(now);
                i:=p[s[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (pd[j]=false) and (b[i].f>0) then begin
                        dst[j]:=dst[s[now]]+1;
                        pd[j]:=true;
                        if j=n*m*2+1 then exit(true);
                        inc(head);
                        s[head]:=j;
                    end;
                    i:=b[i].next;
                end;
            end;
            exit(pd[n*m*2+1]);
        end;
    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 dinic:longint;
        var
            num:longint;
        begin
            num:=0;
            while bfs=true do
                num:=num+change(0,maxlongint);
            exit(num);
        end;
    begin
        readln(n,m,r,c);
        fillchar(p,sizeof(p),-1);
        fillchar(b,sizeof(b),0);
        len:=-1;
        for i:=1 to n do
            for j:=1 to m do begin
                getchar(ch);
                if ch='.' then bo[i,j]:=true else bo[i,j]:=false;
            end;
        for i:=1 to n do
            for j:=1 to m do begin
                if (i+c<=n) and (j+r<=m) and (bo[i,j]=true) and (bo[i+c,j+r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j+r+n*m,1);
                if (i+r<=n) and (j+c<=m) and (bo[i,j]=true) and (bo[i+r,j+c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j+c+n*m,1);
                if (i+c<=n) and (j-r>0) and (bo[i,j]=true) and (bo[i+c,j-r]=true) then
                    add(i*m+j-m,(i+c)*m-m+j-r+n*m,1);
                if (i+r<=n) and (j-c>0) and (bo[i,j]=true) and (bo[i+r,j-c]=true) then
                    add(i*m+j-m,(i+r)*m-m+j-c+n*m,1);
            end;
        tot:=0;
        for i:=1 to n do
            for j:=1 to m do
                if bo[i,j]=true then begin
                    inc(tot);
                    add(0,i*m-m+j,1);
                    add(i*m-m+j+n*m,n*m*2+1,1);
                end;
        writeln(tot-dinic);
    end.       
Category: 最大流 | Tags:
9
18
2013
1

【BZOJ3275】Number【最小割】

开始把题目看错了,然后就在纠结要不要拆点。后来仔细一看,发现是‘同时满足’,然后便是赤果果的最小割了。把所有数分成奇数和偶数两组,因为奇数之间不满足1,偶数之间不满足2.然后从源点向偶数连流量为其大小的边,从奇数向汇连流量为其大小的边。如果奇数和偶数之间不能同时选那么就连一条流量无穷大的边。这样做出来的最小割满足矛盾的点对中只选一个,而且其流量就是要舍弃的数字的大小和。于是乎我们用总权值把最小割减减掉即可。

 

program p3275;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		b:array[0..500000] of bian;
		p,dst,x,s:array[0..5000] of longint;
		pd:array[0..5000] of boolean;
		len,n,i,j,tot:longint;
	function gcd(k1,k2:longint):longint;
		begin
			if k2=0 then exit(k1);
			exit(gcd(k2,k1 mod k2));
		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
			i,j,k,num:longint;
		begin
			if (k1=n+1) or (k2=0) then exit(k2);
			num:=0;
			i:=p[k1];
			while i<>-1 do begin
				j:=b[i].point;
				if (b[i].f>0) and (dst[j]=dst[k1]+1) then begin
					k:=change(j,min(k2,b[i].f));
					k2:=k2-k; num:=num+k;
					dec(b[i].f,k); inc(b[i xor 1].f,k);
					if k2=0 then break;
				end;
				i:=b[i].next;
			end;
			if num=0 then dst[k1]:=-1;
			exit(num);
		end;
	function bfs:boolean;
		var
			i,j,head,now:longint;
		begin
			fillchar(dst,sizeof(dst),-1);
			fillchar(pd,sizeof(pd),false);
			head:=1; now:=0; pd[0]:=true; s[1]:=0; dst[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[s[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) and (b[i].f>0) then begin
						dst[j]:=dst[s[now]]+1;
						pd[j]:=true;
						if j=n+1 then exit(true);
						inc(head);
						s[head]:=j;
					end;
					i:=b[i].next;
				end;
			end;
			exit(pd[n+1]);
		end;
	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 dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do 
				num:=num+change(0,maxlongint);
			exit(num);
		end;
	begin
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		readln(n);
		tot:=0;
		for i:=1 to n do begin
			read(x[i]);
			tot:=tot+x[i];
		end;
		for i:=1 to n do 
			for j:=1 to n do
				if (x[i] mod 2=0) and (x[j] mod 2=1) and (trunc(sqrt(x[i]*x[i]+x[j]*x[j]))=sqrt(x[i]*x[i]+x[j]*x[j])) and (gcd(x[i],x[j])=1) then
					add(i,j,maxlongint);
		for i:=1 to n do 
			if x[i] mod 2=0 then add(0,i,x[i]) else add(i,n+1,x[i]);
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags:
9
4
2013
0

【BZOJ1497】【NOI2006】最大获利【最大流】

最大权闭合子图,最大流水掉

program p1497;
	const
		maxn=1000000;
	type
		bian=record
			next,point,f:longint;
		end;
	var
		p,dst,x:array[0..100000] of longint;
		pd:array[0..60000] of boolean;
		b:array[0..1000000] of bian;
		tot,n,m,i,j,len,k1,k2,k3:longint;
	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 bfs:boolean;
		var
			head,now,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			x[1]:=0; pd[0]:=true; dst[0]:=0; head:=1; now:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if (pd[j]=false) and (b[i].f>0) then begin
						dst[j]:=dst[x[now]]+1;
						pd[j]:=true;
						if j=n+m+1 then exit(true);
						inc(head);
						x[head]:=j;
					end;
					i:=b[i].next;
				end;
			end;
			exit(pd[n+m+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
			i,j,num,ans,k:longint;
		begin
			if (k1=n+m+1) or (k2=0) then exit(k2);
			ans:=0; i:=p[k1];
			while i<>-1 do begin
				j:=b[i].point;
				if (dst[j]=dst[k1]+1) and (b[i].f>0) then begin
					k:=change(j,min(k2,b[i].f));
					dec(k2,k); inc(ans,k);
					inc(b[i xor 1].f,k); dec(b[i].f,k);
					if k2=0 then break;
				end;
				i:=b[i].next;
			end;
			if ans=0 then dst[k1]:=-1;
			exit(ans);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while bfs=true do 
				num:=num+change(0,maxn);
			exit(num);
		end;
	begin
		readln(n,m);
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=1 to n do begin
			read(k1);
			add(i,n+m+1,k1);
		end;
		tot:=0;
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(n+i,k1,maxn);
			add(n+i,k2,maxn);
			add(0,n+i,k3);
			tot:=tot+k3;
		end;
		writeln(tot-dinic);
	end.
Category: 最大流 | Tags:
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:
7
31
2013
1

【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:
7
31
2013
1

【BZOJ1266】【AHOI2006】上学路线route【最小割+最短路】



program p1266;
	type
		bian=record
			first,next,point,f,w,bo:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,d,dst:array[1..100000] of longint;
		x:array[1..1000000] of longint;
		pd:array[1..100000] of boolean;
		k1,k2,k3,k4,len,i,j,n,m:longint;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].first:=k1;
			b[len].w:=k3;
			b[len].f:=k4;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,k3,0);
		end;
	procedure spfa;
		var
			head,now,i,j:longint;
		begin
			fillchar(pd,sizeof(pd),false);
			fillchar(x,sizeof(x),0);
			fillchar(d,sizeof(d),$3f);
			head:=1; now:=0; x[1]:=n; d[n]:=0; pd[n]:=true;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i<>-1 do begin
					j:=b[i].point;
					if d[j]>d[x[now]]+b[i].w then begin
						d[j]:=d[x[now]]+b[i].w;
						if pd[j]=false then begin
							pd[j]:=true;
							inc(head);
							x[head]:=j;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;
		end;
	procedure dfs(k:longint);
		var
			i,j:longint;
		begin
			pd[k]:=true;
			if k=n then exit;
			i:=p[k];
			while i<>-1 do begin
				j:=b[i].point;
				if (d[j]+b[i].w=d[k]) and (b[i].f>0) then begin
					b[i].bo:=1;
					b[i xor 1].bo:=1;
					if pd[j]=false then dfs(j);
				end;
				i:=b[i].next;
			end;
		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[1]:=true; head:=1; now:=0; x[1]:=1; dst[1]:=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,' ',b[i].bo);
					readln;}
					if (pd[k1]=false) and (b[i].f>0) and (b[i].bo>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) and (b[now].bo>0) 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 begin
				num:=num+change(1,maxlongint);
			end;
			exit(num);
		end;
	begin
		readln(n,m);
		len:=-1;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3,k4);
			add(k1,k2,k3,k4);
			add(k2,k1,k3,k4);
		end;
		spfa;
		writeln(d[1]);
		{for i:=1 to n do
			write(d[i],' ');
		writeln;}
		fillchar(pd,sizeof(pd),false);
		dfs(1);
		{for i:=1 to len do
			writeln(b[i].first,' ',b[i].point,' ',b[i].w,' ',b[i].bo,' ',b[i].f);}
		writeln(dinic);
	end.

先做一次SPFA,然后就可以求出家到学校的最短路图(由所有最短路构成的图),在这个图上做最小割,流量为C,答案就是正解。

Category: 最大流 | Tags:
7
31
2013
1

【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:

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