jiry_2's Blog

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

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的因素）。