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: | Read Count: 1143

登录 *


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