POJ 1149 PIGS(最大流)

POJ 1149 PIGS(最大流)

http://poj.org/problem?id=1149

题意:

有M个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依次来了N个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）

分析:

我的思路也是看大牛的报告来的,<<网络流建模汇总>>:

http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html

大体思路是:

添加一个源点s(编号0)和汇点t(编号n+1),已经n个顾客节点(编号1到n).

1.对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。

2.从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

3.对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i 个顾客向第i + 1 个顾客连一条边，容量为∞。(因为只要前后两个顾客的猪圈有交集,那么前一个顾客上一把能买但是没买的猪都能通过合理的调度而传递给下一个顾客,且无数量限制)

AC代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=100+5;
const int maxm=1000+5;

struct Edge
{
    int from,to,cap,flow;
    Edge(){}
    Edge(int f,int t,int c,int flow):from(f),to(t),cap(c),flow(flow){}
};

struct Dinic
{
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n,int s,int t)
    {
        this->n=n, this->s=s, this->t=t;
        edges.clear();
        for(int i=0;i<n;i++) G[i].clear();
    }

    void AddEdge(int from,int to,int cap)
    {
        edges.push_back( Edge(from,to,cap,0) );
        edges.push_back( Edge(to,from,0,0) );
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        vis[s]=true;
        Q.push(s);
        d[s]=0;
        while(!Q.empty())
        {
            int x=Q.front(); Q.pop();
            for(int i=0;i<G[x].size(); ++i)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow)
                {
                    vis[e.to]=true;
                    d[e.to] = d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0) return a;
        int flow=0,f;

        for(int& i =cur[x];i<G[x].size();++i)
        {
            Edge& e=edges[G[x][i]];
            if(d[e.to]==d[x]+1 && (f=DFS(e.to, min(a,e.cap-e.flow) ))>0 )
            {
                e.flow+=f;
                edges[G[x][i]^1].flow -=f;
                flow+=f;
                a-=f;
                if(a==0) break;
            }
        }
        return flow;
    }
    int Max_Flow()
    {
        int ans=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            ans+=DFS(s,INF);
        }
        return ans;
    }
}DC;

int pig_num[maxm];//每个猪圈的猪初始数目
vector<int> pighouse[maxm];//pighouse[i]保存的是第i个猪圈中按序访问的顾客

int main()
{
    int M,N;
    while(scanf("%d%d",&M,&N)==2)
    {
        for(int i=1;i<=M;i++) pighouse[i].clear();
        DC.init(N+2,0,N+1);
        for(int i=1;i<=M;i++)
            scanf("%d",&pig_num[i]);
        for(int i=1;i<=N;i++)
        {
            int num;
            scanf("%d",&num);
            while(num--)
            {
                int pighouse_id;
                scanf("%d",&pighouse_id);
                pighouse[pighouse_id].push_back(i);
            }
            int v;
            scanf("%d",&v);
            DC.AddEdge(i,N+1,v);//节点到汇点的边
        }
        int val[maxn];//val保存源点到节点边的容量
        memset(val,0,sizeof(val));
        for(int i=1;i<=M;i++)
        {
            val[pighouse[i][0]]+= pig_num[i];
            for(int j=0;j<pighouse[i].size()-1;j++)
            {
                DC.AddEdge(pighouse[i][j],pighouse[i][j+1],INF);//前后顾客之间的边
            }
        }
        for(int i=1;i<=N;i++)if(val[i])
            DC.AddEdge(0,i,val[i]);//源点到顾客之间的边
        printf("%d\n",DC.Max_Flow());
    }
    return 0;
}