洛谷 P4001 [ICPC-Beijing 2006] 狼抓兔子

题目链接

链接

题解

首先这道题是裸的最大流，但是如果直接套用最大流算法明显会 TLE，我们可以利用本题的特殊性质来解决。

有关概念

（摘自 浅析最大最小定理在信息学竞赛中的应用） 平面图的性质：

1. 如果一个连通的平面图有\(n\)个点，\(m\)条边和\(f\)个面，那么\(f=m-n+2\)；

2. 对于每一个平面图\(G\)，都有一个对偶图\(G'\)与之对应： 图\(G\)一个面为图\(G'\)中的一个点； 图\(G\)中一条边： 若属于两个面，图\(G'\)中两个面所对应的点之间连边； 若只属于一个面，图\(G'\)中构造那个面所对应的点连向自己的回边。 于是：\(G\)和\(G'\)边数相同，\(G'\)中的环与\(G\)中的割一一对应。

样例 平面图\(G\)

对偶图\(G'\) S-T 平面图：图中的一个点为源点\(S\)，另一个点为汇点\(T\)，且\(S\)和\(T\)都在图中无界面的边界上。

求解方法

先对原图进行一些改造：

在图\(G\)中\(S\)和\(T\)之间连一条边，将原来的无界面分成两部分。

再构造对偶图，将图\(G\)中两个无界面在图\(G'\)中对应的两个点分别视为\(S'\)和\(T'\)，两个点之间不连边；

构造样例的对偶图：

可以发现一个\(S’\)到\(T'\)之间的路径对应图\(G\)的一个割，再考虑容量的话就可以发现\(S'\)-\(T'\)的最短路即是原图的最小割。

最后利用最大流-最小割定理求得答案。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=2000000,INF=0x3f3f3f3f;
int n,m,nn,head[MAXN],d[MAXN],cnt;
bool vis[MAXN];
struct edge
{
    int v,next,val;
}e[MAXN*3];
void addedge(int x,int y,int z)
{
    e[++cnt]=(edge){y,head[x],z};
    head[x]=cnt;
    return;
}
void inedge()
{
    int x,cnt;
    //横边
    for(int i=1;i<=m-1;i++)
    {
        scanf("%d",&x);
        addedge(0,i,x);addedge(i,0,x);
    }
    cnt=(m-1)*2;
    for(int i=2;i<n;i++)
    {
        for(int j=1;j<=m-1;j++)
        {
            cnt++;
            scanf("%d",&x);
            addedge(cnt,cnt-m+1,x);addedge(cnt-m+1,cnt,x);
        }
        cnt+=(m-1);
    }
    for(int i=1;i<=m-1;i++)
    {
        scanf("%d",&x);
        addedge(nn,nn-m+i,x);addedge(nn-m+i,nn,x);
    }
    //竖边
    cnt=m;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d",&x);
        addedge(cnt,nn,x);addedge(nn,cnt,x);
        for(int j=2;j<m;j++)
        {
            cnt++;
            scanf("%d",&x);
            addedge(cnt,cnt-m,x);addedge(cnt-m,cnt,x);
        }
        scanf("%d",&x);
        addedge(0,cnt-m+1,x);addedge(cnt-m+1,0,x);
        cnt+=m;
    }
    //斜边
    cnt=0;
    for(int i=1;i<=n-1;i++)
    {
        for(int j=1;j<=m-1;j++)
        {
            cnt++;
            scanf("%d",&x);
            addedge(cnt,cnt+m-1,x);addedge(cnt+m-1,cnt,x);
        }
        cnt+=(m-1);
    }
    return;
}
void SPFA()
{
    queue<int>q;
    q.push(0);
    vis[0]=true;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=false;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(d[u]+e[i].val<d[v])
            {
                d[v]=d[u]+e[i].val;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&m);
    if(n==1)
    {
        int x,ans=INF;
        for(int i=1;i<=m-1;i++)
        {
            scanf("%d",&x);
            ans=min(ans,x);
        }
        printf("%d\n",ans==INF?0:ans);
        return 0;
    }
    else if(m==1)
    {
        int x,ans=INF;
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d",&x);
            ans=min(ans,x);
        }
        printf("%d\n",ans==INF?0:ans);
        return 0;
    }
    nn=(n-1)*(m-1)*2+1;
    inedge();
    for(int i=1;i<=nn;i++)d[i]=INF;
    SPFA();
    printf("%d\n",d[nn]);
    return 0;
}