poj1149PIGS——网络最大流

题目：http://poj.org/problem?id=1149

不把猪圈当做点，而把顾客当作点，把猪当作边权(流量)；

因为猪圈中的猪可流动，所以共用一个猪圈的人互相连边；

注意应该连成链的形式，来保证先后顺序。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

queue<int>q;

int m,n,s[],head[],ct=,cur[],hd[],inf=1e9,d[],ans;

bool sid[][];

struct N{

    int to,next,w;

    N(int t=,int n=,int ww=):to(t),next(n),w(ww) {}

}edge[];

bool in[];

void add(int x,int y,int z)

{

    sid[x][y]=;sid[y][x]=;

    edge[++ct]=N(y,head[x],z);head[x]=ct;

    edge[++ct]=N(x,head[y],);head[y]=ct;

}

int fd(int x,int y)

{

    for(int i=head[y];i;i=edge[i].next)//此处为有向边，所以应找y边集中连到x的边！

        if(edge[i].to==x)return i;

    return ;

}

bool bfs()

{

    memset(d,,sizeof d);

    while(q.size())q.pop();

    d[]=;q.push();

    while(q.size())

    {

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

        for(int i=head[x];i;i=edge[i].next)

        {

            int u=edge[i].to;

            if(!d[u]&&edge[i].w)

            {

                d[u]=d[x]+;

                q.push(u);

            }

        }

    }

    return d[n+];

}

int dfs(int x,int f)

{

    if(x==n+)return f;

    int res=;

    for(int i=cur[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(d[u]==d[x]+&&edge[i].w)

        {

            int tmp=dfs(u,min(edge[i].w,f-res));

            edge[i].w-=tmp;

            edge[i^].w+=tmp;

            res+=tmp;

            if(edge[i].w)cur[x]=i;

            if(res==f)return f;

        }

    }

    if(!res)d[x]=;

    return res;

}

int main()

{

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

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

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

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

    {

        int k,x;

        scanf("%d",&k);

        for(int j=;j<=k;j++)

        {

            scanf("%d",&x);

            if(!hd[x]&&!in[i])hd[x]=i,in[i]=,add(,i,s[x]);

            else if(!hd[x]&&in[i])

            {

                hd[x]=i;

                int e=fd(i,);

                edge[e].w+=s[x];

//                edge[e^1].w-=s[x];//!!!

            }

//            if(!hd[x])hd[x]=i,add(0,i,s[x]);

            if(hd[x])

            {

                if(!sid[hd[x]][i])//免重

                    add(hd[x],i,inf);

                hd[x]=i;//!!!成链

            }

        }

        scanf("%d",&x);

        add(i,n+,x);

    }

    while(bfs())

    {

        for(int i=;i<=n+;i++)cur[i]=head[i];

        ans+=dfs(,inf);

    }

    printf("%d",ans);

    return ;

}