原题传送门

整理了下之前A的题

平面图可以转化成对偶图，然后（NlogN）的可以求出图的最小割（最大流）

算法合集有具体的讲解，有兴趣的可以在网上搜下或者向我要（QQ30056882）

/**************************************************************    Problem: 1001    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:4124 ms    Memory:158960 kb****************************************************************/ //By BLADEVILvar    n, m                    :longint;    pre, other, len, last   :array[0..6001000] of longint;    l                       :longint;    heng, shu, xie          :array[0..2010,0..2010] of longint;    tot                     :longint;    st, fin                 :longint;    que, d                  :array[0..2000010] of longint;    flag                    :array[0..2000010] of boolean;     procedure connect(x,y,z:longint);begin    inc(l);    pre[l]:=last[x];    last[x]:=l;    other[l]:=y;    len[l]:=z;end;     procedure init;var    i, j                    :longint;    min                     :longint;begin    read(n,m);    for i:=1 to n do        for j:=1 to m-1 do read(heng[i,j]);         for i:=1 to n-1 do        for j:=1 to m do read(shu[i,j]);             for i:=1 to n-1 do        for j:=1 to m-1 do read(xie[i,j]);    min:=maxlongint;    if (n=1) or (m=1) then    begin        for i:=1 to n do            for j:=1 to m do            begin                if heng[i,j]>0 then if min>heng[i,j] then min:=heng[i,j];                if shu[i,j]>0 then if min>shu[i,j] then min:=shu[i,j];                if xie[i,j]>0 then if min>xie[i,j] then min:=xie[i,j];            end;        writeln(min);        halt;    end;    tot:=2*(m-1)*(n-1);    for i:=1 to tot do    if i mod 2=0 then    begin        if ((i mod (2*(m-1)))>0) then        begin            connect(i,i+1,shu[i div (2*(m-1))+1,(i mod (2*(m-1))) div 2+1]);            connect(i+1,i,shu[i div (2*(m-1))+1,(i mod (2*(m-1))) div 2+1]);        end;        if (i-2*m+1>0) then            if ((i mod (2*(m-1)))>0) then            begin                connect(i,i-2*m+1,heng[i div (2*(m-1))+1,(i mod (2*(m-1))) div 2]);                 connect(i-2*m+1,i,heng[i div (2*(m-1))+1,(i mod (2*(m-1))) div 2]);            end else            begin                connect(i,i-2*m+1,heng[i div (2*(m-1)),m-1]);                   connect(i-2*m+1,i,heng[i div (2*(m-1)),m-1]);            end;    end else    begin        connect(i,i+1,xie[i div (2*(m-1))+1,((i mod (2*(m-1)))+1) div 2]);        connect(i+1,i,xie[i div (2*(m-1))+1,((i mod (2*(m-1)))+1) div 2]);    end;    st:=tot+1; fin:=tot+2;    for i:=1 to (m-2) do    begin        connect(st,i*2,heng[1,i]);        connect(i*2,st,heng[1,i]);    end;    for i:=2 to (n-1) do    begin        connect(st,i*2*(m-1),shu[i,m]);        connect(i*2*(m-1),st,shu[i,m]);    end;    connect(st,2*(m-1),shu[1,m]);       connect(st,2*(m-1),heng[1,m-1]);        connect(2*(m-1),st,shu[1,m]);    connect(2*(m-1),st,heng[1,m-1]);    for i:=2 to (m-1) do    begin        connect((n-2)*2*(m-1)+2*i-1,fin,heng[n,i]);        connect(fin,(n-2)*2*(m-1)+2*i-1,heng[n,i]);    end;    for i:=1 to (n-2) do    begin        connect(fin,(i-1)*2*(m-1)+1,shu[i,1]);        connect((i-1)*2*(m-1)+1,fin,shu[i,1]);    end;    connect(fin,(n-2)*2*(m-1)+1,shu[(n-1),1]);    connect(fin,(n-2)*2*(m-1)+1,heng[n,1]);    connect((n-2)*2*(m-1)+1,fin,shu[(n-1),1]);    connect((n-2)*2*(m-1)+1,fin,heng[n,1]);end;  procedure main;var    i, j                    :longint;    h, t                    :longint;    cur                     :longint;    q, p                    :longint;     begin    que[1]:=st;     filldword(d,sizeof(d) div 4,maxlongint div 10);    d[st]:=0;    t:=1; h:=0;    while h<>t do    begin        h:=h mod 2000000+1;        cur:=que[h];        flag[cur]:=false;        q:=last[cur];        while q<>0 do        begin            p:=other[q];            if d[cur]+len[q]