链接：http://poj.org/problem?id=1149

题意：迈克有一个养猪场，有m个猪圈，每个猪圈都上了锁，但是迈克没有钥匙他不能打开猪圈，要买猪的顾客一个接一个来养猪场，每个人有一些猪圈的钥匙，他们要买一定数目的猪，如果顾客要来买猪，他们会提前告诉迈克：他们所拥有的钥匙数量及对应哪些猪圈、要购买的数量，这样迈克就能安排销售计划使卖出的猪最多。

当每个顾客来的时候，将那些他拥有钥匙的猪圈门全部打开，迈克从猪圈中卖出一些猪给他们，如果迈克愿意，他可以重新分配这些被打开的猪圈中的猪，当顾客离开时猪圈再次被锁上。猪圈可容纳的猪无上限。求迈克这一天最多能卖多少猪。

昨天下午开始看网络流，看了很久，感觉理解了增广路的方法和预流推进的方法，不过一下接触的概念太多，有点迷糊。。。今天终于能做题了，看到这道题，毫无想法。。。终于知道了为什么大家都说网络流建图难，剩下的套模板就行了。我现在连模板都不会敲，更别说建图了。参考图论书上的解法和代码，一点一点理解了这道题，但是思路是书上的，代码是照着书上敲的。。

分析：

本题的关键在于如何构造一个容量网络。在本题中，容量网络的构造方法如下：

1)  将顾客看作除源点和汇点以外的结点，另设2个结点：源点和汇点；

2)  源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目；

3)  若源点和某个结点之间有重边，则将权合并（因此源点流出的流量就是所有的猪圈能提供的猪的数目）；
4)  顾客j紧跟在顾客i之后打开某个猪圈，则边<i, j>的权是+∞；这是因为，如果顾客j紧跟在顾客i 之后打开某个猪圈，那么迈克就有可能根据顾客j 的需求将其他猪圈中的猪调整到该猪圈，这样顾客j 就能买到尽可能多的猪；

5)  每个顾客和汇点之间连边，边的权是顾客所希望购买的猪的数目（因此汇点的流入量就是每个顾客所购买的猪的数目）。

这是建图的思路，是图论书上的，对熟练掌握网络最大流的人来说，剩下的就比较简单了，不过对我来说，代码还得照着书一点点敲。

算法用的是增广路的算法，没有使用DFS，我把书中自己写的队列改成了stl的队列，剩下基本都和书里一样

作为我第一道照着书敲下来的网络流题目，我把注释都写的很详细

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int s,t;    //s源点，t汇点
int customer[110][110];       //节点间容量
int flow[110][110];           //节点间流量
int pigs[1010];                 //每个猪圈中猪的数量
int last[1010];                 //每个猪圈前一个顾客的序号
int n,m;                        //n顾客数目，m猪圈数目
void ford(){
    int prev[110];   //增广路上该顶点前一个顶点的序号，初始为-2未标号，源点标号-1
    int minflow[110];   //每个顶点的可改进量α
    minflow[0] = INF;
    int p;
    queue<int>q;
    while(1){   //标号法
        for(int i=0;i<110;i++)  prev[i] = -2;
        prev[0] = -1;
        while(!q.empty())   q.pop();
        q.push(0);
        while(!q.empty()&&prev[t]==-2){
            int v = q.front();
            q.pop();
            for(int i=0;i<t+1;i++){
                //如果顶点i是顶点v的邻接顶点，则考虑是否对顶点i进行标号
                //customer[v][i]-flow[v][i]!=0能保证顶点i是顶点v的邻接顶点且能标号
                if(prev[i]==-2&&(p=customer[v][i]-flow[v][i])){  //顶点i未标号，且Cij-Fij>0
                    prev[i] = v;
                    q.push(i);
                    minflow[i] = min(minflow[v],p);
                }
            }
        }
        if(prev[t]==-2) break;  //汇点t没有标号，标号法结束
        int j;
        for(int i=prev[t],j=t;i!=-1;j=i,i=prev[i]){ //调整增广路流量
            flow[i][j] = flow[i][j] + minflow[t];
            flow[j][i] = -flow[i][j];
        }
    }
    p = 0;
    for(int i=0;i<t;i++)    //统计进入汇点的流量，即为最大流的流量
        p = p + flow[i][t];
    printf("%d\n",p);
}
int main(){
    int k,num;          //k第k个猪圈的钥匙，num每个顾客拥有钥匙的数目
    int i,j;
    memset(last,0,sizeof(last));
    memset(customer,0,sizeof(customer));
    memset(flow,0,sizeof(flow));
    scanf("%d%d",&m,&n);
    s = 0;
    t = n + 1;
    for(i=1;i<=m;i++)   scanf("%d",&pigs[i]);
    for(i=1;i<=n;i++){  //构造网络流
        scanf("%d",&num);
        for(j=0;j<num;j++){
            scanf("%d",&k);
            if(last[k]==0)  //第i个顾客是第k个猪圈的第一个顾客
                customer[s][i] = customer[s][i] + pigs[k];
            else        //顾客i紧跟在顾客last[k]后面打开第k个猪圈
                customer[last[k]][i] = INF;
            last[k] = i;
        }
        scanf("%d",&customer[i][t]);    //每个顾客到汇点的边，权值为顾客购买猪的数量
    }
    ford();
    return 0;
}