题目链接：
POJ1149
题意：
麦克是农场主有N个猪圈，每个猪圈都有一把锁但麦克没有钥匙。要买猪的顾客一个接一个来到养猪场，每个顾客有一些猪圈的钥匙，而且他们要买一定数量的猪。当每个顾客到来时，他将那些他拥有钥匙的猪圈全部打开；迈克从这些猪圈中挑出一些猪卖给他们；如果迈克愿意，迈克可以重新分配这些被打开的猪圈中的猪；当顾客离开时，猪圈再次被锁上。给出每个猪圈的初始的猪的数量，求麦克能卖出猪的最大数量
思路：
注意顾客是一个接一个有顺序来的
网络流以顾客为节点建模
1) 将顾客看作除源点和汇点以外的结点，另设2 个结点：源点和汇点；2) 源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目；3) 若源点和某个结点之间有重边，则将权合并（因此源点流出的流量就是所有的猪圈能提供的猪的数目）；4) 顾客j 紧跟在顾客i 之后打开某个猪圈，则边<i, j>的权是+∞；这是因为，如果顾客j 紧跟在顾客i 之后打开某个猪圈，，那么迈克就有可能根据顾客j 的需求将其他猪圈中的猪调整到该猪圈，这样顾客j 就能买到尽可能多的猪；5) 每个顾客和汇点之间连边，边的权是顾客所希望购买的猪的数目（因此汇点的流入量就是每个顾客所购买的猪的数目）。
代码：
#include<iostream>#include<cstdio>#include<cstring>#define M 305#define maxx 0x3f3f3f3fusing namespace std;int level[M];int edge[M][M];int init[1005];int vis[1005];int n;void Init(){memset(vis,0,sizeof(vis));memset(edge,0,sizeof(edge));}int min(int a,int b){return a<b?a:b;}int bfs(){int q[M];int v,head=0,tail=0;memset(level,-1,sizeof(level));q[tail++]=0;level[0]=0;while(head<tail){v=q[head++];for(int i=0;i<=n+1;i++)if(level[i]==-1&&edge[v][i]){level[i]=level[v]+1;q[tail++]=i;}}return level[n+1]!=-1;}int dfs(int loc,int flow){int unused=flow;if(flow==0||loc==n+1)return flow;for(int i=0;i<=n+1;i++)if(level[i]==level[loc]+1&&edge[loc][i]){int used=dfs(i,min(unused,edge[loc][i]));edge[loc][i]-=used;edge[i][loc]+=used;unused-=used;}return flow-unused;}int main(){int m;while(~scanf("%d%d",&m,&n)){Init();for(int i=1; i<=m; i++)scanf("%d",&init[i]);int num,id,need;for(int i=1; i<=n; i++){scanf("%d",&num);for(int j=1;j<=num;j++){scanf("%d",&id);if(!vis[id])edge[0][i]+=init[id];elseedge[vis[id]][i]+=maxx;vis[id]=i;}scanf("%d",&need);edge[i][n+1]=need;}int ans=0;while(bfs())ans+=dfs(0,maxx);cout<<ans<<endl;}return 0;}
曾经一直想让别人知道自己的心情，那些沉重，
