bzoj1001平面图最小割转对偶图最短路

https://www.lydsy.com/JudgeOnline/problem.php?id=1001

很明显的求对偶图的最短路即可（由于特判写错了一直wa = = ）

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

struct edge{

    int to,Next;ll c;

}e[maxn];

int head[N],cnt;

void init()

{

    cnt=;

    memset(head,-,sizeof head);

}

void add(int u,int v,ll c)

{

//    printf("%d %d %lld\n",u,v,c);

    e[cnt].to=v;

    e[cnt].c=c;

    e[cnt].Next=head[u];

    head[u]=cnt++;

}

priority_queue<pli,vector<pli>,greater<pli> >q;

ll dis[N];

void dij(int s)

{

    for(int i=;i<N;i++)dis[i]=1e18;

    dis[s]=;

    q.push(mp(,s));

    while(!q.empty())

    {

        pil u = q.top();q.pop();

        int x=u.se;

        if(dis[x]<u.fi)continue;

        for(int i=head[x];~i;i=e[i].Next)

        {

            int To=e[i].to;

            if(dis[To]>dis[x]+e[i].c)

            {

                dis[To]=dis[x]+e[i].c;

                q.push(mp(dis[To],To));

            }

        }

    }

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s=(n-)*(m-)*,t=(n-)*(m-)*+;

    if(n<=&&m<=)return *puts("");

    else if(n==||m==)

    {

        ll ans=1e18;

        for(int i=;i<=(n==?m-:n-);i++)

        {

            ll x;scanf("%lld",&x);

            ans=min(ans,x);

        }

        printf("%lld\n",ans);

        return ;

    }

    init();

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m-;j++)

        {

            ll x;scanf("%lld",&x);

            if(i==)

            {

                add(s,*((i-)*(m-)+j-),x);

                add(*((i-)*(m-)+j-),s,x);

            }

            else if(i==n)

            {

                add(t,*((i-)*(m-)+j-)+,x);

                add(*((i-)*(m-)+j-)+,t,x);

            }

            else

            {

                add(*((i-)*(m-)+j-)+,*((i-)*(m-)+j-),x);

                add(*((i-)*(m-)+j-),*((i-)*(m-)+j-)+,x);

            }

        }

    }

    for(int i=;i<=n-;i++)

    {

        for(int j=;j<=m;j++)

        {

            ll x;scanf("%lld",&x);

            if(j==)

            {

                add(t,*((i-)*(m-))+,x);

                add(*((i-)*(m-))+,t,x);

            }

            else if(j==m)

            {

                add(s,*((i-)*(m-)+m-),x);

                add(*((i-)*(m-)+m-),s,x);

            }

            else

            {

                add(*((i-)*(m-)+j-),*((i-)*(m-)+j-)+,x);

                add(*((i-)*(m-)+j-)+,*((i-)*(m-)+j-),x);

            }

        }

    }

    for(int i=;i<=n-;i++)

    {

        for(int j=;j<=m-;j++)

        {

            ll x;scanf("%lld",&x);

            ll now=(i-)*(m-)+j-;

            add(*now,*now+,x);

            add(*now+,*now,x);

        }

    }

    dij(s);

    printf("%lld\n",dis[t]);

    return ;

}

/********************

********************/