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: | Read Count: 1799
Avatar_small
Maha 11th Model Pape 说:
2022年8月16日 02:50

Every year, this board administers the 11th grade test, and the Maha 11th Important Question Paper for this examination will soon be available on the Maharashtra Board's official website. Around 15 lakh students took part in the Maharashtra Board Class 11th examinations, which were likewise held in the month of February starting in March 2023. Maha 11th Model Paper 2023 The Maharashtra Board Class 11th Important Question Paper 2023 was released in the month of May 2023. According to a poll, Maharashtra 11th Important Question Paper 2023 is expected to be released in May of this year as well. We advise all students to be patient and wait for the release of the Important Question Paper 2023.


登录 *


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