语文挂科了，所以来除草了。
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的因素）。
