平面图求最小割；
其实看bzoj1001一开始着实把我怔住了
AC的人暴多，可自己完全没思路
后来看了某大牛的ppt，才会做
一个月前做这题的吧，今天来简单回忆一下；
首先是欧拉公式
如果一个连通的平面图有n个点，m条边和f个面，那么f=m-n+2
我们把原图的每个面看成新图的一个点，对于原图中的每条边
如果边只属于一个面，那么给对应点连一个自环；
如果边两侧各有一个面，那么给对应点之间连一条无向边
这样，新图与原图的边一一对应；
可以发现，新图的一条路径对应原图的一个割
于是我们原图起点终点连一条边，增加一个附加面（也可以理解为把外面言直线st分为两个面）；
按上述方法建新图，于是最小割问题转化为对新图求最短路；
最短路可以用堆优化dij；
这题我的dij+heap写的有进步
const inf=;
type link=^node;
node=record
po,len:longint;
next:link;
end;
point=record
num,loc:longint;
end; var w:array[..] of link;
heap:array[..] of point;
where,d:array[..] of longint;
xie,hen,shu:array[..,..] of longint;
t,s,i,j,n,m,x,y:longint;
p:link; procedure swap(var a,b:point);
var c:point;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y,z:longint);
var p:link;
begin
new(p);
p^.po:=y;
p^.len:=z;
p^.next:=w[x];
w[x]:=p;
end; procedure up(i:longint);
var j,x,y:longint;
begin
j:=i shr ;
while j> do
begin
if heap[i].num<heap[j].num then
begin
x:=heap[i].loc;
y:=heap[j].loc;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=i shr ;
end
else break;
end;
end; procedure sift(i:longint);
var j,x,y:longint;
begin
j:=i shl ;
while j<=s do
begin
if (j+<=s) and (heap[j].num>heap[j+].num) then inc(j);
if heap[i].num>heap[j].num then
begin
x:=heap[i].loc;
y:=heap[j].loc;
where[x]:=j;
where[y]:=i;
swap(heap[i],heap[j]);
i:=j;
j:=i shl ;
end
else break;
end;
end; procedure build; //复杂的建图，这种东西一定要谨慎，错误才会少；
var i:longint;
begin
for i:= to m- do
begin
add(,i+,hen[,i]);
add(i+,,hen[,i]);
end;
for i:= to n- do
begin
x:=(m-)*(*i-)+;
add(,x,shu[i,m]);
add(x,,shu[i,m]);
end; for i:= to m- do
begin
x:=t-m+i;
add(t,x,hen[n,i]);
add(x,t,hen[n,i]);
end;
for i:= to n- do
begin
x:=(m-)*(*i-)+;
add(t,x,shu[i,]);
add(x,t,shu[i,]);
end; for i:= to n- do
for j:= to m- do
begin
x:=(*i-)*(m-)+j+;
y:=x+m-;
add(x,y,hen[i,j]);
add(y,x,hen[i,j]);
end; for i:= to n- do
for j:= to m- do
begin
x:=(*i-)*(m-)+j;
y:=x+m;
add(x,y,shu[i,j]);
add(y,x,shu[i,j]);
end; for i:= to n- do
for j:= to m- do
begin
x:=(*i-)*(m-)+j+;
y:=x+m-;
add(x,y,xie[i,j]);
add(y,x,xie[i,j]);
end;
end; procedure dij; //最短路
var p:link;
mid,k,y:longint;
begin
p:=w[];
for i:= to t do
d[i]:=inf;
d[]:=;
while p<>nil do
begin
x:=p^.po;
d[x]:=min(d[x],p^.len);
p:=p^.next;
end;
s:=;
for i:= to t do
begin
inc(s);
heap[s].num:=d[i];
heap[s].loc:=i; //表示堆的这个位置是哪个点
where[i]:=s; //where表示这个点在堆的哪个位置
up(s);
end; for k:= to t do
begin
mid:=heap[].num;
if s= then break;
if mid=inf then break;
x:=heap[].loc;
y:=heap[s].loc;
where[y]:=; swap(heap[],heap[s]); //退堆
dec(s); sift();
p:=w[x];
while p<>nil do
begin
y:=p^.po;
if d[y]>p^.len+mid then //更新，入堆
begin
d[y]:=p^.len+mid;
heap[where[y]].num:=d[y];
up(where[y]);
end;
p:=p^.next;
end;
end;
end; begin
readln(n,m);
for i:= to n do
begin
for j:= to m- do
read(hen[i,j]);
end;
for i:= to n- do
begin
for j:= to m do
read(shu[i,j]);
end;
for i:= to n- do
begin
for j:= to m- do
read(xie[i,j]);
end; if n= then //注意这种情况要特判
begin
t:=inf;
for i:= to m- do
t:=min(hen[,i],t);
writeln(t);
halt;
end
else if m= then
begin
t:=inf;
for i:= to n- do
t:=min(t,shu[i,]);
writeln(t);
halt;
end;
t:=(n-)*(m-)*+; //计算新图总点数
build;
dij;
writeln(d[t]);
end.