BZOJ 1001: [BeiJing2006]狼抓兔子 求平面图的最小割

题面

题意

给出一幅无向平面图,求s到t的最小割.

对偶图:将原图中的每一块区域当作一个点,原图上的每一条边转化为这条边两边区域之间的一条边,任何只在顶点处有交点的图(平面图)都有对偶图.

做法

这道题如果直接跑最大流,复杂度显然不对,但因为它存在对偶图,我们可以将题目转化为求左下角这块到右上角这块的最短路,对于样例可以这么建图

首先建对偶图

之后去掉原图就可以得到

可以发现从0点到13点((n-1)*(m-1) *2+1)的最短路恰好为最小割,这也是对偶图的一个性质,因此只要跑一边迪杰斯特拉即可.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define C ch=getchar()
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define mp make_pair<int,int>
#define fi first
#define se second
#define N 1000100
using namespace std;

int n,m,first[N<<],bb,t,s,d[N<<];
bool vis[N<<];
char ch;
P tmp;
struct Bn
{
    int to,next,quan;
} bn[N*];
priority_queue<P,vector<P>,greater<P> >pq;

inline int read()
{
    int res;
    for(C;ch<'0';C);
    for(res=ch-'0',C;ch>='0';res=res*+ch-'0',C);
    return res;
}

inline int ask(int u,int v,int w)
{
    return (u-)*(n-)*+(v-)*+w+;
}

inline void add(int u,int v,int w)
{
    bb++;
    bn[bb].to=v;
    bn[bb].next=first[u];
    bn[bb].quan=w;
    first[u]=bb;
}

inline void ad(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,w);
}

int main()
{
    memset(first,-,sizeof(first));
    int i,j,p,q;
    m=read(),n=read();
    t=(m-)*(n-)*+;
    for(i=; i<=m; i++)
    {
        for(j=; j<n; j++)
        {
            p=read();
            i==?ad(ask(,j,),t,p):i==m?ad(ask(m-,j,),s,p):ad(ask(i-,j,),ask(i,j,),p);
        }
    }
    for(i=; i<m; i++)
    {
        for(j=; j<=n; j++)
        {
            p=read();
            j==?ad(s,ask(i,j,),p):j==n?ad(ask(i,n-,),t,p):ad(ask(i,j-,),ask(i,j,),p);
        }
    }
    for(i=; i<m; i++)
    {
        for(j=; j<n; j++)
        {
            ad(ask(i,j,),ask(i,j,),read());
        }
    }
    memset(d,,sizeof(d));
    pq.push(mp(,s));
    d[s]=;
    for(; !pq.empty()&&!vis[t];)
    {
        tmp=pq.top();
        pq.pop();
        q=tmp.se;
        if(vis[q]) continue;
        vis[q]=;
        for(p=first[q]; p!=-; p=bn[p].next)
        {
            if(d[bn[p].to]>d[q]+bn[p].quan)
            {
                d[bn[p].to]=d[q]+bn[p].quan;
                pq.push(mp(d[bn[p].to],bn[p].to));
            }
        }
    }
    cout<<d[t];
}