题目大意

源点为 (1,1)，汇点为 (n,m) (上图中n=4,m=4)。有以下三种类型的道路

• (x, y) <==> (x+1, y)

• (x, y) <==> (x, y+1)

• (x, y) <==> (x+1, y+1)

每条无向边边权＞0，求最小割。

数据范围

$1\leqslant n,m\leqslant 1000$

题解

平面图最大流

可以把每一个面作为一个点，如果原图一条边$k$分割了两个面$A,B$

那么从A向B连一条无向边，边权与边$k$边权相等

把外平面分成两个平面，一个作为起点一个作为终点，同样建边

要求是使得新图的一条路径对应原图的一个割

那么跑一次最短路就等于原图的最小割。

关于平面图最大流的知识可以看《两极相通——浅析最大—最小定理在信息学竞赛中的应用》

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
#define maxn 3000000
using namespace std;

struct edge{int to,next,c;}e[maxn*2+500];
int last[maxn+500];
int flag[maxn+500],dis[maxn+500];
int n,m,et,nm,u,v,tot;
inline void addedge(int u,int v,int c){
    e[++et].to=v;e[et].next=last[u];e[et].c=c;last[u]=et;
    e[++et].to=u;e[et].next=last[v];e[et].c=c;last[v]=et;
}

inline void spfa(){
    queue <int> q;
    memset(dis,inf,sizeof(dis));
    q.push(0);dis[0]=0;flag[0]=1;
    while(!q.empty()){
        int h=q.front();q.pop();flag[h]=0;
        goedge(i,h)
            if (dis[h]+e[i].c<dis[e[i].to]){
                dis[e[i].to]=dis[h]+e[i].c;
                if (!flag[e[i].to]){flag[e[i].to]=1;q.push(e[i].to);}
            }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    nm=2*(n-1)*(m-1)+1;
    For(i,1,n)
        For(j,1,m-1){
            int c;scanf("%d",&c);++tot;
            u=2*(tot-m+1);v=2*tot-1;
            if (i==1) u=0;if (i==n) v=nm;
            addedge(u,v,c);
        }
    tot=0;
    For(i,1,n-1)
        For(j,1,m){
            int c;scanf("%d",&c);++tot;
            u=2*tot-3;v=2*tot;
            if (j==1) u=nm;if (j==m) {v=0;tot--;}
            addedge(u,v,c);
        }
    tot=0;
    For(i,1,n-1)
        For(j,1,m-1){
            int c;scanf("%d",&c);++tot;
            u=2*tot-1;v=2*tot;
            addedge(u,v,c);
        }
    spfa();
    printf("%d\n",dis[nm]);
    return 0;
}