首页 > 代码库 > poj1149 PIGS 最大流(神奇的建图)

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=1110;const int M=2*N*N, INF=1000000;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=0;    for(i=1;i<=n;i++)        cure[i]=head[i];    numh[0]=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^1].w+=flow;            }            ans+=flow;            u=neck;        }        for(i=cure[u];i!=-1;i=edge[i].next)            if(edge[i].w && h[u]==h[edge[i].to]+1) break;        if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}        else        {            if(0==--numh[h[u]]) break; //GAP优化            cure[u]=head[u];            for(tmp=n,i=head[u];i!=-1;i=edge[i].next)                if(edge[i].w) tmp=min(tmp, h[edge[i].to]);            h[u]=tmp+1;            ++numh[h[u]];            if(u!=s) u=pre[u];        }    }}void init(){    tot=0;    memset(head,-1,sizeof(head));    memset(pre,-1,sizeof(pre));    memset(h,0,sizeof(h));    memset(numh,0,sizeof(numh));    memset(vis,0,sizeof(vis));    memset(flag,0,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=0;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+1; e=s+1;        for(i=1;i<=m;i++)        {            scanf("%d",&pg[i]);        }        for(k=1;k<=n;k++)        {            scanf("%d",&a);            for(i=0;i<a;i++)            {                scanf("%d",&j);                if(!vis[j])//猪圈j没有打开过                {                    if(!flag[k]) //顾客k没有打开过猪圈                    {                        addedge(s,k,pg[j]);                        flag[k]=tot-2;//-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 0;}
View Code

 

poj1149 PIGS 最大流(神奇的建图)