?id=1149
题目描述： 迈克在一个养猪场工作，养猪场里有M 个猪圈，每个猪圈都上了锁。由于迈克没有钥匙，所以他不能打开任何一个猪圈。要买猪的顾客一个接一个来到养猪场，每个顾客有一些猪圈的钥匙，，而且他们要买一定数量的猪。某一天，所有要到养猪场买猪的顾客，他们的信息是要提前让迈克知道的。这些信息包括：顾客所拥有的钥匙（详细到有几个猪圈的钥匙、有哪几个猪圈的钥匙）、要购买的数量。这样对迈克很有好处，他可以安排销售计划以便卖出的猪的数目最大。更详细的销售过程：当每个顾客到来时，他将那些他拥有钥匙的猪圈全部打开；迈克从这些猪圈中挑出一些猪卖给他们；如果迈克愿意，迈克可以重新分配这些被打开的猪圈中的猪；当顾客离开时，猪圈再次被锁上。注意：猪圈可容纳的猪的数量没有限制。编写程序，计算迈克这一天能卖出猪的最大数目。
输入格式为： 1) 第一行是两个整数：M 和N（1≤M≤1000，1≤N≤100）。M 是猪圈的数目，N 是顾客 的数目。猪圈的编号从1 到M，顾客的编号从1 到N。 2) 第二行是M 个整数，为每个猪圈中初始时猪的数目，范围是[0，1000]。 3) 接下来的N 行是顾客的信息，第i 个顾客的信息保存在第i+2 行。格式为：A K1 K2…KAB。A 为拥有钥匙的数目，Kj 表示拥有第Kj 个猪圈的钥匙，B 为该顾客想买的猪的数目。A，B 均可为0。
输出描述： 输出有且仅有一行，为迈克能够卖掉的猪的最大数目。
大神的博客写得很清楚
Dinic 852K 32MS G++ 2028B
maxn=1100,maxm=1100,INF=0x3f3f3f3f;;struct Edge{int from,to,cap,flow;};vector<Edge> edges;vector<int> G[maxn];int d[maxn],cur[maxn],pig[maxm],last[maxn];bool vis[maxn];int n,m,s,t;inline void addedge(int u,int v,int c){edges.push_back((Edge){u,v,c,0});edges.push_back((Edge){v,u,0,0});int x=edges.size();G[u].push_back(x-2);G[v].push_back(x-1);}bool BFS(){memset(vis,0,sizeof(vis));queue<int> Q;Q.push(s);d[s]=0;vis[s]=1;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]=1;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[x]+1==d[e.to]&&(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;}void Dinic(){int flow=0;while(BFS()){memset(cur,0,sizeof(cur));flow+=DFS(s,INF);}cout<<flow<<endl;}void Init(){memset(last,0,sizeof(last));cin>>m>>n;s=0,t=n+1;for(int i=1;i<=m;++i) scanf(“%d”,&pig[i]);int num,x,c;for(int i=1;i<=n;++i){scanf(“%d”,&num);while(num–){scanf(“%d”,&x);if(last[x]==0)addedge(0,i,pig[x]);elseaddedge(last[x],i,INF);last[x]=i;}scanf(“%d”,&c);addedge(i,n+1,c);}}int main(){Init();Dinic();return 0;
年轻是我们唯一拥有权利去编织梦想的时光
