题目链接

题面：

题解：
平面图最小割=平面图最大流=其对偶图最短路。
之前用网络流写过一次，据说卡dinic，也被我乱搞搞过去了。

还不如我用dinic最大流跑得快。。这就离谱。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

char buffer[100001],*S,*T;
inline char Get_Char()
{
    if (S==T)
    {
        T=(S=buffer)+fread(buffer,1,100001,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read()
{
    char c;int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
    return re;
}

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=6000100;
const int maxm=100100;
const int up=1000;

int head[maxn],ver[maxn],edge[maxn],nt[maxn],tot=1;
int d[maxn],s,t;
bool ha[maxn];

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=z,nt[tot]=head[y],head[y]=tot;
}

int dij(void)
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    priority_queue<pair<int,int> >q;
    q.push(pr(0,s));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(pr(-d[y],y));
            }
        }
    }
    return d[t];
}

void build(int n,int m)
{
    int x;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            x=read();
            if(i==1) add(j,t,x);
            else if(i==n) add((2*i-3)*(m-1)+j,s,x);
            else add((2*i-3)*(m-1)+j,(2*i-2)*(m-1)+j,x);
        }
    }

    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            x=read();
            if(j==1) add((i*2-1)*(m-1)+1,s,x);
            else if(j==m) add((i*2-1)*(m-1),t,x);
            else add((i*2-2)*(m-1)+j-1,(i*2-1)*(m-1)+j,x);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            x=read();
            add((i*2-2)*(m-1)+j,(i*2-1)*(m-1)+j,x);
        }
    }
}

int main(void)
{
    int n,m;
    n=read(),m=read();
    s=(n*2-2)*(m-1)+1;
    t=s+1;
    build(n,m);
    printf("%d\n",dij());
    return 0;
}