jiry_2's Blog

这道题是一道很裸最小割，但是由于数据范围太大，所以要用最短路来实现。建图比较诡异，详情看代码。

program p1001;
	type
		bian=record
			point,next,w:longint;
		end;
		d=record
			po,w:longint;
		end;
	var
		p,f:array[0..3000000] of longint;
		b:array[1..9000000] of bian;
		x:array[1..3000000] of d;
		pd:array[0..2000000] of boolean;
		maxn,k1,k2,k3,n,m,i,j,len,t1,t2:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].w:=k3;
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure charu(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function mi(k1,k2:longint):longint;
		begin
			if x[k1].w>x[k2].w then exit(k2) else exit(k1);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(mi(mi(k1,k2),k3));
		end;
	procedure press(k:longint);
		var
			k1:longint;
			k2:d;
		begin
			k1:=min(k,k*2,k*2+1);
			if k1=k then exit;
			k2:=x[k1];
			x[k1]:=x[k];
			x[k]:=k2;
			press(k1);
		end;
	procedure find(k:longint);
		var
			k1:d;
		begin
			if k=1 then exit;
			if x[k div 2].w>x[k].w then begin
				k1:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=k1;
				find(k div 2);
			end;
		end;
	function dijstra:longint;
		var
			k1,k2,k3,i,j,now,len:longint;
			k:d;
		begin
			fillchar(pd,sizeof(pd),true);
			fillchar(x,sizeof(x),$7f);
			maxn:=x[1].po; len:=1;
			fillchar(f,sizeof(f),$3f);
			x[1].po:=0; x[1].w:=0; f[0]:=0;
			while len>0 do begin
				len:=len-1;
				k:=x[1];
				if len>0 then begin
					x[1]:=x[len+1];
					x[len+1].w:=maxn;
					press(1);
				end;
				if pd[k.po]=false then continue;
				pd[k.po]:=false;
				k2:=p[k.po];
				while k2>0 do begin
					k1:=b[k2].point;
					if f[k.po]+b[k2].w<f[k1] then begin
						f[k1]:=f[k.po]+b[k2].w;
						inc(len);
						x[len].po:=k1; x[len].w:=f[k1];
						find(len);
					end;
					k2:=b[k2].next;
				end;
			end;
			exit(f[t2]);
		end;
	begin
		readln(n,m);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		t1:=(n-1)*(m-1);
		t2:=t1*2+1;
		if (n=1) and (m=1) then begin
			writeln(0);
			exit;
		end;
		for i:=1 to n do
			for j:=1 to m-1 do begin
				read(k1);
				if i=1 then k2:=0 else k2:=(i-2)*(m-1)+j+t1;
				if i=n then k3:=t2 else k3:=(i-1)*(m-1)+j;
				charu(k2,k3,k1);
			end;
		for i:=1 to n-1 do
			for j:=1 to m do begin
				read(k1);
				if j=1 then k2:=t2 else k2:=(i-1)*(m-1)+j-1;
				if j=m then k3:=0 else k3:=(i-1)*(m-1)+j+t1;
				charu(k2,k3,k1);
			end;
		for i:=1 to n-1 do
			for j:=1 to m-1 do begin
				read(k1);
				k2:=(i-1)*(m-1)+j;
				k3:=(i-1)*(m-1)+j+t1;
				charu(k2,k3,k1);
			end;
		writeln(dijstra);
	end.