poj1149 PIGS 最大流（神奇的建图）

　　一开始不看题解，建图出错了。后来发现是题目理解错了。

　　 if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.

　　题目中的这句话非常关键，没理解就错掉了。有很多人写的题解只告诉我们怎么做，却没告诉我们为什么要那样做。

　　这句话是的意思是可以重组打开过的猪圈。也就是当客人打开猪圈（他能打开的都打开了）以后，他选择了需要买的猪以后，Mirko可以随意把剩下的猪分配到打开的猪圈中。当然，我们追求的是最好的分配方式。

　　下面来分析样例是怎么来的：

　　第一个顾客打了了第一、第二个猪圈，选择了两头猪。剩下两头猪。Mirko把这两头猪全部放进了第二个猪圈。根据第三步，可以知道这是最好的分配方式。

　　第二个顾客打开了第一、第三个猪圈以后，选走了3头。剩下的猪随便分配到第一、第三个猪圈对后面没影响。

　　第三个顾客打开了第二个猪圈，买走两头。（最多只能有两头，就是第一步分配的）。

　　2+3+2=7

　　明白了题意，然后才去向怎么建图。建图的方法其他人的博客里写得非常好了。可以参考他们的.

　　http://blog.csdn.net/wangjian8006/article/details/7932947 这个博客里有一个网络流建模汇总的链接，可以去下载http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html

　　http://www.cnblogs.com/-sunshine/archive/2012/08/21/2648683.html

　　下面是我的代码：建图用的是链式前向星

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=;

const int M=*N*N, INF=;

struct node

{

    int to,next,w;

}edge[M];

int head[N],numh[N],h[N],cure[N],pre[N],vis[N],flag[N];

int ans,tot;

void SAP(int s, int e,int n)

{

    int flow,u,tmp,neck,i;

    ans=;

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

        cure[i]=head[i];

    numh[]=n;

    u=s;

    while(h[s]<n)

    {

        if(u==e)

        {

            flow =INF;

            for(i=s;i!=e;i=edge[cure[i]].to)

            {

                if(flow>edge[cure[i]].w)

                {

                    neck=i;

                    flow =edge[cure[i]].w;

                }

            }

            for(i=s;i!=e;i=edge[cure[i]].to)

            {

                tmp=cure[i];

                edge[tmp].w-=flow;

                edge[tmp^].w+=flow;

            }

            ans+=flow;

            u=neck;

        }

        for(i=cure[u];i!=-;i=edge[i].next)

            if(edge[i].w && h[u]==h[edge[i].to]+) break;

        if(i!=-) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}

        else

        {

            if(==--numh[h[u]]) break; //GAP优化

            cure[u]=head[u];

            for(tmp=n,i=head[u];i!=-;i=edge[i].next)

                if(edge[i].w) tmp=min(tmp, h[edge[i].to]);

            h[u]=tmp+;

            ++numh[h[u]];

            if(u!=s) u=pre[u];

        }

    }

}

void init()

{

    tot=;

    memset(head,-,sizeof(head));

    memset(pre,-,sizeof(pre));

    memset(h,,sizeof(h));

    memset(numh,,sizeof(numh));

    memset(vis,,sizeof(vis));

    memset(flag,,sizeof(flag));

}

void addedge(int i,int j,int w)

{

    edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;

    edge[tot].to=i;edge[tot].w=;edge[tot].next=head[j];head[j]=tot++;

}

int pg[N];

int main()

{

    //猪圈的编号1 ~m ,人的编号是m+1 ~ m+n

    //freopen("test.txt","r",stdin);

    int m,n,i,j,k,a,b,t,s,e;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        init();

        s=n+; e=s+;

        for(i=;i<=m;i++)

        {

            scanf("%d",&pg[i]);

        }

        for(k=;k<=n;k++)

        {

            scanf("%d",&a);

            for(i=;i<a;i++)

            {

                scanf("%d",&j);

                if(!vis[j])//猪圈j没有打开过

                {

                    if(!flag[k]) //顾客k没有打开过猪圈

                    {

                        addedge(s,k,pg[j]);

                        flag[k]=tot-;//-2别弄错了

                    }

                    else

                    {

                        edge[flag[k]].w+=pg[j];

                    }

                    vis[j]=k;

                }

                else

                {

                    addedge(vis[j],k,INF);

                    vis[j]=k;

                }

            }

            scanf("%d",&b);

            addedge(k,e,b);

        }

        SAP(s,e,e);

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

    }

    return ;

}

巴特西

poj1149 PIGS 最大流（神奇的建图）

最新文章

热门文章