10
16
2013
1

【BZOJ2007】【Noi2010】海拔【最小割+最短路】

语文挂科了,所以来除草了。

program p2007;

	type
		d=record
			w,po:int64;
		end;
		bian=record
			next,point,w:int64;
		end;
	var
		b:array[1..1000000] of bian;
		i,j,n,k1,k2,len:longint;
		x:array[1..1000000] of d;
		p,f:array[0..1000000] of int64;
		pd:array[0..1000000] of boolean;
		maxn:int64;
	procedure add(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].next:=p[k1];
			b[len].point:=k2;
			b[len].w:=k3;
			p[k1]:=len;
		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[n*n+1]);
        end;
	begin
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		len:=0;
		readln(n);
		for i:=1 to n+1 do
			for j:=1 to n do begin
				readln(k1);
				if i=1 then 
					add(j,n*n+1,k1)
				else if i=n+1 then
					add(0,n*(n-1)+j,k1)
				else add(n*(i-1)+j,n*(i-2)+j,k1);
			end;
		for i:=1 to n do begin
			readln(k1);
			add(0,n*i-n+1,k1);
			for j:=1 to n-1 do begin
				readln(k1);
				add(n*i-n+j,n*i-n+j+1,k1);
			end;
			readln(k1);
			add(n*i,n*n+1,k1);
		end;
		for i:=1 to n+1 do
			for j:=1 to n do begin
				readln(k1);
				if (i<>1) and (i<>n+1) then add(n*(i-2)+j,n*(i-1)+j,k1);
			end;
		for i:=1 to n do begin
			readln(k1);
			for j:=1 to n-1 do begin
				readln(k1);
				add(n*i-n+j+1,n*i-n+j,k1);
			end;
			readln(k1);
		end;
		fillchar(x,sizeof(x),$3f);
		fillchar(f,sizeof(f),$3f);
		maxn:=x[1].po;
		writeln(dijstra);
	end.

一眼就可以看出来是最小割,因为显而易见每个点的高度只可能是0或1,那么它们必有一个交接面,而这个就需要用最小割了。但是最小割会T80,所以要用对偶图+最短路来解决最小割问题,就如BZOJ1001。而这题恶心的把SPFA卡了,我又都比的把DJ+堆敲炸了,这道题就坑了我一个晚上QAQ(虽然有OSU和CS的因素)。

 

Category: 最短路 | Tags:
9
4
2013
0

【BZOJ1491】【NOI2007】社交网络【弗洛伊德】

两个弗洛伊德+乘法原理,第二个弗洛伊德居然写错了。。调了半天才调出来,QAQ

program p1491;
	var
		b,f:array[1..300,1..300] of int64;
		w:array[1..300] of extended;
		n,m,i,j,k1,k2,k3,k:longint;
	begin
		fillchar(f,sizeof(f),0);
		fillchar(b,sizeof(b),$3f);
		readln(n,m);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			if k3<b[k1,k2] then begin
				b[k1,k2]:=k3;
				b[k2,k1]:=k3;
				f[k1,k2]:=1;
				f[k2,k1]:=1;
			end;
		end;
		for k:=1 to n do 
			for i:=1 to n do
				for j:=1 to n do begin
					if (i=j) or (j=k) or (k=i) then continue;
					if b[i,k]+b[k,j]<b[i,j] then begin
						b[i,j]:=b[i,k]+b[k,j];
						f[i,j]:=f[i,k]*f[k,j];
					end else if b[i,k]+b[k,j]=b[i,j] then
						f[i,j]:=f[i,j]+f[i,k]*f[k,j];
				end;
		fillchar(w,sizeof(w),0);
		for k:=1 to n do
			for i:=1 to n do
				for j:=1 to n do
					if (i<>k) and (j<>k) and (b[i,k]+b[k,j]=b[i,j])and (i<>j)then
						w[k]:=w[k]+f[i,k]*f[k,j]/f[i,j];
		for i:=1 to n do
			writeln(w[i]:0:3);
	end.
Category: 最短路 | Tags:
7
30
2013
1

【BZOJ1001】【BeiJing2006】狼抓兔子【最小割+最短路】

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



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.
				
Category: 最短路 | Tags:

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