8
17
2013
0

【BZOJ1003】【ZJOI2006】物流运输trans【最短路+DP】

以天为状态,则f[i]=min(dj[1,i]*i,dj[j,i]*(i-j+1)+k+f[j-1](2<=j<=i)),dj[i,j]表示第i天到第j天均走同样的路线时的最短路。不需要初始化,在过程中要用到位运算来降低时间复杂度,详细见代码。

 



program p1003;
	type
		bian=record
			next,point,w:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,two,d:array[1..30] of longint;
		x,f:array[0..200] of int64;
		len,i,j,n,m,k,e,q,k1,k2,k3,maxn:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function min(k1,k2:int64):int64;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findmin:longint;
		var
			i,j,k:longint;
		begin
			k:=maxlongint; j:=0;
			for i:=1 to m do
				if (d[i]<k) and (d[i]<>-1) then begin
					k:=d[i];
					j:=i;
				end;
			exit(j);
		end;
	procedure push(k1,k2:longint);
		var
			i,j:longint;
		begin
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if (b[i].w+d[k1]<d[j]) and (k2 and two[j]=0) then 
					d[j]:=b[i].w+d[k1];
				i:=b[i].next;
			end;
			d[k1]:=-1;
		end;
	function dj(k:longint):longint;
		var
			i,j,now:longint;
		begin
			fillchar(d,sizeof(d),$3f);
			d[1]:=0;
			for i:=1 to m do begin
				now:=findmin;
				if now=m then exit(d[m]);
				push(now,k);
			end;
		end;
	begin
		readln(n,m,k,e);
		len:=0;
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		for i:=1 to e do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
		end;
		two[1]:=1;
		for i:=2 to m do
			two[i]:=two[i-1]*2;
		readln(q);
		fillchar(x,sizeof(x),0);
		for i:=1 to q do begin
			readln(k1,k2,k3);
			for j:=k2 to k3 do
				x[j]:=x[j] or two[k1];
		end;
		fillchar(f,sizeof(f),$3f);
		maxn:=f[1];
		f[0]:=0;
		for i:=1 to n do begin
			k1:=x[i];
			for j:=i downto 2 do begin
				k2:=dj(k1);
				if k2<>maxn then begin
					f[i]:=min(f[i],k2*(i-j+1)+k+f[j-1]);
					k1:=k1 or x[j-1];
				end else break;
			end;
			k2:=dj(k1);
			if k2<>maxn then f[i]:=min(f[i],k2*i);
		end;
		writeln(f[n]);
	end.
Category: DP | Tags:
8
4
2013
0

【BZOJ2662】【BeiJing wc2012】冻结【分层图+最短路】

类似于2763,不过层与层之间的边权要改为原边权的一半。我直接改了这个细节贴2763的代码了。

program p2662;
	type
		bian=record
			next,point,w:longint;
		end;
		heap=record
			dis,point:longint;
		end;
	var
		p,d:array[1..200000] of longint;
		x:array[1..200000] of heap;
		b:array[1..1500000] of bian;
		ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
		now:heap;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].w:=k3;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function minn(k1,k2:longint):longint;
		begin
			if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(minn(k1,minn(k2,k3)));
		end;
	procedure press(k:longint);
		var
			i:longint;
			j:heap;
		begin
			i:=min(k,k*2,k*2+1);
			if i=k then exit;
			j:=x[k]; x[k]:=x[i]; x[i]:=j;
			press(i);
		end;
	procedure find(k:longint);
		var
			i:heap;
		begin
                        if k=1 then exit;
			if x[k].dis<x[k div 2].dis then begin
				i:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=i;
				find(k div 2);
			end;
		end;
	procedure push(k:heap);
		var
			i,j:longint;
		begin
			i:=p[k.point];
			while i<>0 do begin
				j:=b[i].point;
				if k.dis+b[i].w<d[j] then begin
					d[j]:=k.dis+b[i].w;
					inc(len);
					x[len].point:=j;
					x[len].dis:=d[j];
					find(len);
				end;
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m,k);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,k3 div 2);
				ade(j*n+k2,j*n+k1+n,k3 div 2);
				add(j*n+n+k1,j*n+n+k2,k3);
			end;
		end;
		fillchar(d,sizeof(d),$3f);
		fillchar(x,sizeof(x),$7f);
		maxn:=x[1].dis;
		s:=1; t:=n;
		len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
		while len>0 do begin
			dec(len);
			now:=x[1];
			if len>0 then begin
				x[1]:=x[len+1];
				x[len+1].dis:=maxn;
				press(1);
			end;
			push(now);
		end;
		ans:=maxlongint;
		for i:=0 to k do
			if d[i*n+t]<ans then ans:=d[i*n+t];
		writeln(ans);
	end.
Category: 分层图 | Tags:
8
4
2013
0

【BZOJ2763】【JLOI2011】飞行路线【分层图+最短路】

把原图复制K+1遍,如果原来点I,J之间有边就在第P层的I向P+1层J连一条有向边,同理,第P层的点J向P+1层I连一条有向边。以第一层S为原点做最短路,答案就是所有层T点距离的最小值。应注意SPFA会T,应该用DJ+HEAP。

program p2736;
	type
		bian=record
			next,point,w:longint;
		end;
		heap=record
			dis,point:longint;
		end;
	var
		p,d:array[1..200000] of longint;
                x:array[1..200000] of heap;
		b:array[1..3000000] of bian;
		ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
		now:heap;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].w:=k3;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function minn(k1,k2:longint):longint;
		begin
			if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(minn(k1,minn(k2,k3)));
		end;
	procedure press(k:longint);
		var
			i:longint;
			j:heap;
		begin
			i:=min(k,k*2,k*2+1);
			if i=k then exit;
			j:=x[k]; x[k]:=x[i]; x[i]:=j;
			press(i);
		end;
	procedure find(k:longint);
		var
			i:heap;
		begin
                        if k=1 then exit;
			if x[k].dis<x[k div 2].dis then begin
				i:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=i;
				find(k div 2);
			end;
		end;
	procedure push(k:heap);
		var
			i,j:longint;
		begin
			i:=p[k.point];
			while i<>0 do begin
				j:=b[i].point;
				if k.dis+b[i].w<d[j] then begin
					d[j]:=k.dis+b[i].w;
					inc(len);
					x[len].point:=j;
					x[len].dis:=d[j];
					find(len);
				end;
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m,k);
		readln(s,t);
		inc(s); inc(t);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			inc(k1); inc(k2);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,0);
				ade(j*n+k2,j*n+k1+n,0);
				add(j*n+n+k1,j*n+n+k2,k3);
			end;
		end;
		fillchar(d,sizeof(d),$3f);
		fillchar(x,sizeof(x),$7f);
		maxn:=x[1].dis;
		len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
		while len>0 do begin
			dec(len);
			now:=x[1];
			if len>0 then begin
				x[1]:=x[len+1];
				x[len+1].dis:=maxn;
				press(1);
			end;
			push(now);
		end;
		ans:=maxlongint;
		for i:=0 to k do
			if d[i*n+t]<ans then ans:=d[i*n+t];
		writeln(ans);
	end.
Category: 分层图 | Tags:
7
31
2013
0

【BZOJ2539】【Ctsc2000】丘比特的烦恼【KM】

很裸的KM算法,但是数据极其恶心。调了我好几个月才A掉(一开始在VIJOS做,然后跳过,今天重新开始做),要注意的是后面输入的缘分值可能为0,所以要把不能射箭两个人之间连上-maxlongint的边,不能连0。还有就是坐标可能不是整数,应当用浮点型存储。

 



program p2539;
	type
		people=record
			na:string;
			xx,yy:extended;
		end;
    var
        x,y,aimy:array[1..100] of longint;
        vx,vy:array[1..100] of boolean;
        w:array[1..100,1..100] of longint;
		p:array[1..200] of people;
        n,m,i,j,k,a,b,c:longint;
		d:extended;
		ss,s:string;
    function max(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    function min(k1,k2:extended):extended;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function find(k:longint):boolean;
        var
            i,j,kk:longint;
        begin
			if k=0 then exit(false);
            vx[k]:=true;
            for i:=1 to n do
                if (vy[i]=false) and (x[k]+y[i]=w[k,i]) then begin
                    vy[i]:=true; 
                    if (aimy[i]=0) or (find(aimy[i])) then begin
						aimy[i]:=k;
                        exit(true);
                    end;
                end;
			exit(false);
        end;
    begin
		readln(d);
        readln(n);
        for i:=1 to 2*n do begin
			readln(s);
			j:=1;
			while (s[j+1]<>' ') do 
				inc(j);
			val(copy(s,1,j),p[i].xx,a);
			j:=j+2;
			k:=1;
			while (s[j+k]<>' ') do 
				inc(k);
			val(copy(s,j,k),p[i].yy,a);
			p[i].na:=copy(s,j+k+1,length(s)-j-k);
			for j:=1 to length(p[i].na) do 
				p[i].na[j]:=upcase(p[i].na[j]);
		end;
		readln(s);
		for i:=1 to n do
			for j:=1 to n do
				w[i,j]:=1;
		while s<>'End' do begin
			i:=1;
			k:=1;
			while s[i+k]<>' ' do
				inc(k);
			ss:=copy(s,i,k);
			for j:=1 to length(ss) do
				ss[j]:=upcase(ss[j]);
			for a:=1 to 2*n do
				if ss=p[a].na then break;
			i:=i+k+1;
			k:=1;
			while s[i+k]<>' ' do
				inc(k);
			ss:=copy(s,i,k);
			for j:=1 to length(ss) do
				ss[j]:=upcase(ss[j]);
			for b:=1 to 2*n do
				if ss=p[b].na then break;
			val(copy(s,i+k+1,length(s)-i-k),c,j);
			if a>b then w[b,a-n]:=c
				else w[a,b-n]:=c;
			readln(s);
		end;
		for i:=1 to n do
			for j:=1 to n do begin
				if sqr(p[i].xx-p[j+n].xx)+sqr(p[i].yy-p[j+n].yy)>sqr(d) then begin
					w[i,j]:=-1000000000;
					continue;
				end;
				for k:=1 to n*2 do
					if (k<>i) and (k<>j+n) and ((p[i].xx-p[j+n].xx)*(p[i].yy-p[k].yy)=(p[i].yy-p[j+n].yy)*(p[i].xx-p[k].xx))then begin
						if (p[k].xx>max(p[i].xx,p[j+n].xx)) or (p[k].xx<min(p[i].xx,p[j+n].xx)) or (p[k].yy>max(p[i].yy,p[j+n].yy)) or (p[k].yy<min(p[i].yy,p[j+n].yy)) then
							continue;
						w[i,j]:=-1000000000;
						break;
					end;
			end;
		{for i:=1 to n do begin
			for j:=1 to n do
				write(w[i,j],' ');
			writeln;
		end;
}        fillchar(y,sizeof(y),0);
        fillchar(x,sizeof(x),0);
        for i:=1 to n do
            for j:=1 to n do
                x[i]:=trunc(max(x[i],w[i,j])); 
        fillchar(aimy,sizeof(aimy),0);
        for k:=1 to n do
            repeat
				{for i:=1 to n do
					write(aimy[i],' ');
				readln;}
				fillchar(vx,sizeof(vx),false);
                fillchar(vy,sizeof(vy),false);
                if find(k) then break;
                c:=1000000;
                for i:=1 to n do begin
                    if not vx[i] then continue;
                    for j:=1 to n do begin
                        if vy[j] then continue;
                        c:=trunc(min(c,x[i]+y[j]-w[i,j]));
                    end;
                end;
                for i:=1 to n do begin
                    if vx[i] then x[i]:=x[i]-c;
                    if vy[i] then y[i]:=y[i]+c;
                end;
            until false;
        a:=0;
        for i:=1 to n do
            a:=a+w[aimy[i],i];
        writeln(a);
        {for i:=1 to n do
            writeln(aimy[i],' ',w[aimy[i],i]);
        readln;
        readln;}
    end.  
Category: KM | Tags:
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:
7
31
2013
0

【BZOJ2748】【HAOI2012】音量调节【DP】

背包,不用多说了。



program p2748;
	var
		f:array[0..50,0..1000] of boolean;
		x:array[1..100] of longint;
		ans,n,maxn,i,j,k:longint;
	begin
		readln(n,ans,maxn);
		for i:=1 to n do 
			read(x[i]);
		fillchar(f,sizeof(f),false);
		f[0,ans]:=true;
		for i:=1 to n do
			for j:=0 to maxn do begin
				if (j+x[i]<=maxn) and (f[i-1,j]=true) then
					f[i,j+x[i]]:=true;
				if (j-x[i]>=0) and (f[i-1,j]=true) then 
					f[i,j-x[i]]:=true;
			end;
		j:=-1;
		for i:=maxn downto 0 do
			if f[n,i]=true then begin
				j:=i;
				break;
			end;
		writeln(j);
	end.
Category: DP | Tags:
7
31
2013
0

【BZOJ2661】【BeiJing wc2012】连连看【费用流+gcd】



program p2661;
	type
		bian=record
			next,point,w,f:longint;
		end;
	var
		d,p,after:array[0..5000] of longint;
		x:array[1..500000] of longint;
		pd:array[0..5000000] of boolean;
		b:array[0..40000] of bian;
		tot,len,a,c,i,j:longint;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].f:=k3;
			b[len].w:=k4;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,0,-k4);
		end;
	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 spfa:boolean;
		var
			head,now,i,j:longint;
		begin
			head:=1; now:=0;
			fillchar(pd,sizeof(pd),false);
			fillchar(after,sizeof(after),-1);
			fillchar(x,sizeof(x),0);
			fillchar(d,sizeof(d),$3f);
			x[1]:=0; d[0]:=0; pd[0]:=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) and (b[i].f>0) then begin
						d[j]:=d[x[now]]+b[i].w;
						after[j]:=i;
						if pd[j]=false then begin
							pd[j]:=true;
							inc(head);
							x[head]:=j;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=true;
			end;
			if after[c+1]=-1 then exit(false) else exit(true);
		end;
	function change:longint;
		var
			num,ans,i,j:longint;
		begin
			ans:=maxlongint;
			i:=c+1; j:=after[i];
			while j<>-1 do begin
				ans:=min(b[j].f,ans);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			num:=0; i:=c+1; j:=after[i];
			tot:=tot+ans;
			while j<>-1 do begin
				num:=num+ans*b[j].w;
				dec(b[j].f,ans);
				inc(b[j xor 1].f,ans);
				i:=b[j xor 1].point;
				j:=after[i];
			end;
			exit(num);
		end;
	function dinic:longint;
		var
			num:longint;
		begin
			num:=0;
			while spfa=true do
				num:=num+change;
			exit(num);
		end;
	function max(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k2) else exit(k1);
		end;
	begin
		readln(a,c);
		len:=-1;
		tot:=0;
		fillchar(p,sizeof(p),-1);
		fillchar(b,sizeof(b),0);
		for i:=a to c do
			for j:=a to c do
				if (trunc(sqrt(abs(i*i-j*j)))=sqrt(abs(i*i-j*j))) and (i<>j) then begin
					if gcd(trunc(sqrt(abs(i*i-j*j))),min(i,j))=1 then
						add(i,c+j,1,-i-j);
				end;
		for i:=a to c do begin
			add(0,i,1,0);
			add(i+c,c*2+1,1,0);
		end;
		c:=c*2;
		i:=-dinic;
		writeln(tot div 2,' ',i div 2);
	end.

把所有点拆成两个,做一次gcd,把所有满足条件之间的点连上边,构成一个二分图,流量为1,费用为-(x+y),求这个图的最小费用最大流,费用取反然后均除以2即可。

Category: 费用流 | Tags:
7
31
2013
0

【BZOJ2424】【HAOI2010】订货【费用流】

很裸的费用流,不过应当注意题目描述有点问题,它是先把所有东西卖出然后再存入仓库。







program p2424;
	const
		max=10000000;
	type
		bian=record
			w,f,point,next:longint;
		end;
	var
		pd:array[0..100] of boolean;
		x:array[1..1000] of longint;
		after,d,u,l,p:array[0..100] of longint;
		b:array[0..1000] of bian;
		len,i,j,m,n,s:longint;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	procedure ade(k1,k2,k3,k4:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k4;
			b[len].f:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3,k4:longint);
		begin
			ade(k1,k2,k3,k4);
			ade(k2,k1,0,-k4);
		end;
	function change:longint;
		var
			tot,now,i,j,k:longint;
		begin
			k:=max;
			now:=n; 
			while now>0 do begin
				i:=after[now];
				k:=min(k,b[i].f);
				now:=b[i xor 1].point;
			end;
			now:=n; tot:=0;
			while now>0 do begin
				i:=after[now];
				dec(b[i].f,k);
				inc(b[i xor 1].f,k);
				inc(tot,b[i].w*k);
				now:=b[i xor 1].point;
			end;
			exit(tot);
		end;
	function spfa:boolean;
		var
			i,j,now,head:longint;
		begin
			fillchar(x,sizeof(x),0);
			fillchar(pd,sizeof(pd),false);
			fillchar(after,sizeof(after),-1);
			fillchar(l,sizeof(l),$3f);
			head:=1; now:=0; x[1]:=0; pd[0]:=true; l[0]:=0;
			while head>now do begin
				inc(now);
				i:=p[x[now]];
				while i>-1 do begin
					j:=b[i].point;
					if (l[j]>l[x[now]]+b[i].w) and (b[i].f>0) then begin
						l[j]:=l[x[now]]+b[i].w;
						after[j]:=i;
						if pd[j]=false then begin
							inc(head);
							x[head]:=j;
							pd[j]:=true;
						end;
					end;
					i:=b[i].next;
				end;
				pd[x[now]]:=false;
			end;
			if after[n]>-1 then exit(true) else exit(false);
		end;
	function dinic:longint;
		var
			i,j,ans:longint;
		begin
			ans:=0;
			while spfa do 
				ans:=ans+change;
			exit(ans);
		end;
	begin
		readln(n,m,s);
		for i:=1 to n do
			read(u[i]);
		for i:=1 to n do
			read(d[i]);
		fillchar(p,sizeof(p),-1);
		fillchhar(b,sizeof(b),0);
		len:=-1;
		for i:=1 to n do
			add(0,i,max,d[i]);
		for i:=1 to n-1 do
			add(i,i+1,s,m);
		for i:=1 to n do
			add(i,n+1,u[i],0);
		inc(n);
		writeln(dinic);
	end.
Category: 费用流 | Tags:
7
31
2013
0

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

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