poj1149最大流经典构图神题

题意：n个顾客依次来买猪，有n个猪房，每个顾客每次可以开若干个房子，买完时，店主可以调整这位顾客

开的猪房里的猪，共m个猪房，每个猪房有若干猪，求最多能卖多少猪。

构图思想：顾客有先后，每个人想要的猪数量已经确定，显然要建汇点t，每个顾客连线t（以顾客为结点），权值为他想要买

的猪数量（最多想要的都卖了，最大流之归宿，必思汇点！）然后，你想，每个顾客有先后顺序，前一个顾客开过的

房子取的猪数量可以重新分配，必然要连后一个开这个房子的顾客连线（权为inf）（相当于前面一个先取该流量，后面的再取，重新分配）

这样建图！如果没有开过的房子怎么办?建立超级源点啊，权值为房子猪数量。这个可以用一个链来存储，

下面代码中fa【】数组实现之即可，记录前一个开过的顾客号码，没有开过的用s连他。

此题经典啊（被大牛定位较难题），关键是这种构图思想。小结一下：先思源汇点（看最大情况），再思哪些作为结点好，

这题每个结点之间有限制，故在先的结点先取源流，再通向下一个被限制的点，这思想很重要。

关于网上流传的简化图三规则，若是或字关系，是错的：

规律1. 如果几个结点的流量的来源完全相同，则可以把它们合并成一个.

规律2. 如果几个结点的流量的去向完全相同，则可以把它们合并成一个.

规律3. 如果从点u到点v有一条容量为∞的边，并且点v除了点u以外没有别的流量来源，则可以把这两个结点合并成一个.

，符合规则1或2，随便举个例子就错了，我认为1,2合为一条，

必需同时满足才可以合并。

#include<iostream>  //16 ms 1A

#include<cstdio>

#include<queue>

using namespace std;

int m,n;int numpig[1010];int fa[1010];

int e[10000][3];int nume;int head[110];  const int inf=0x3f3f3f3f;

void addedge(int from,int to,int w)

{

    e[nume][0]=to; e[nume][1]=head[from];head[from]=nume;

    e[nume++][2]=w;

    e[nume][0]=from; e[nume][1]=head[to];head[to]=nume;

    e[nume++][2]=0;

}

int level[120];int vis[120];

bool bfs()                 //dinic

{

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

      vis[i]=level[i]=0;

    queue<int>q;q.push(0);

      vis[0]=1;

    while(!q.empty())

    {

        int cur=q.front();q.pop();

        for(int i=head[cur];i!=-1;i=e[i][1])

        {    int v=e[i][0];

             if(!vis[v]&&e[i][2]>0)

             {

                 level[v]=level[cur]+1;

                 if(v==1+n)return 1;

                 vis[v]=1;

                 q.push(v);

             }

        }

    }

    return vis[1+n];

}

int dfs(int u,int minf)

{

    if(u==1+n||minf==0)return minf;

    int sumf=0,f;

    for(int i=head[u];i!=-1&&minf;i=e[i][1])

    {    int v=e[i][0];

        if(level[v]==level[u]+1&&e[i][2]>0)

       {

           f=dfs(v,minf<e[i][2]?minf:e[i][2]);

           e[i][2]-=f;e[i^1][2]+=f;

           minf-=f;sumf+=f;

       }

    }

    return sumf;

}

int dinic()

{

    int sum=0;

    while(bfs())

    {

        sum+=dfs(0,inf);

    }

    return sum;

}

int main()

{

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

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

      {

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

          fa[i]=0;

      }

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

         head[i]=-1;

    nume=0;

     int numkey,house,numwant;

    for(int i=1;i<=n;i++)        //构图

    {

        scanf("%d",&numkey);

        while(numkey--)

        {

            scanf("%d",&house);

            addedge(fa[house],i,fa[house]==0?numpig[house]:inf);

            fa[house]=i;

        }

        scanf("%d",&numwant);

        addedge(i,n+1,numwant);

    }

    int ans=dinic();

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

       return 0;

}

巴特西

poj1149最大流经典构图神题

最新文章

热门文章