#1001. [BeiJing2006]狼抓兔子

这道题要求的是最小割，但是用网络流的话明显太大了，看了网上的资料，才发现对于平面图（！！！），可以将网络流转化成最短路的方式，在网络流中，我们将一个点看成节点，将边权当作最大容量，而转化为最短路后，我们将区域看成一个节点，将两个区域之间的边权看成费用，求最短路就相当于求最小割了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL long long
#define ull unsigned long long
#define PI acos(-1.0)
#define eps 1e-12
#define fi first
#define se second
#define MEM(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define wz cout<<"-----"<<endl;
#define pb push_back
#define mp make_pair
#define pll pair <LL, LL>
#define pii pair <int, int>
#define rep(i,x) for(int i=1;i<=x;i++)
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;
 
const ll maxn = 1e5 + 10, MOD = 1e9 + 7;
const int Move[4][2] = {-1,0,1,0,0,1,0,-1};
const int Move_[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
 
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
const int N=3e6;
const int M=7e6+10;
struct edge{
    ll to,ne,w;
}e[M];
int head[N],cnt;
void add(int x,int y,ll w){
    e[cnt].to=y,e[cnt].ne=head[x],e[cnt].w=w,head[x]=cnt++;
}
ll dis[N];bool vis[N];
struct node{
    ll dis,pos;
    bool operator <(const node &x)const{
        return x.dis<dis;
    }
};
priority_queue<node> st;
ll dij(int S,int T){
    memset(dis,0x3f,sizeof dis);
    dis[S]=0;
    st.push({0,S});
    while(!st.empty()){
        node tep=st.top();st.pop();
        int x=tep.pos;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];~i;i=e[i].ne){
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w){
                dis[y]=dis[x]+e[i].w;
                if(!vis[y])st.push({dis[y],y});
            }
        }
    }
    return dis[T];
}
int main(){
    memset(head,-1,sizeof head);
    int S,T;S=1,T=2234560;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<m;j++){
            int w=read();
            int f,t;
            if(i==n)f=S;
            else f=(i-1)*(m-1)+j<<1;
            if(i==1)t=T;
            else t=(i-2)*(m-1)+j<<1|1;
            add(f,t,w);
            add(t,f,w);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            int w=read();
            int f,t;
            if(j==1)f=S;
            else f=(i-1)*(m-1)+j-1<<1;
            if(j==m)t=T;
            else t=(i-1)*(m-1)+j<<1|1;
            add(f,t,w);
            add(t,f,w);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            int w=read();
            int f,t;
            f=(i-1)*(m-1)+j<<1|1;
            t=(i-1)*(m-1)+j<<1;
            add(f,t,w);
            add(t,f,w);
        }
    }
    cout<<dij(S,T)<<endl;
    return 0;
}