题目链接：ヾ(≧∇≦*)ゝ
Description
Emmy在一个养猪场工作。这个养猪场有M个锁着的猪圈，但Emmy并没有钥匙。
顾客会到养猪场来买猪，一个接着一个。每一位顾客都会有一些猪圈的钥匙，他们会将这些猪圈打开并买走固定数目的猪。所有顾客有的钥匙和他们需要买猪的数量在事先都告诉了Emmy，于是Emmy要订一个计划，使得卖出去的猪最多。
买卖的过程是这样的：一个顾客前来，并打开所有他可以打开的猪圈。然后Emmy从这些猪圈里牵出固定数目的猪卖给顾客（最多只能和顾客需要数相等），并可以重新安排这些开着的猪圈中的猪。
每个猪圈可以存放任意数目的猪。
写一个程序，使得Emmy能够卖出去尽可能多的猪。
Input
第一行有两个整数：M和N，表示猪圈数和顾客数。
第二行有M个整数，表示每个猪圈初始时有多少猪。
接下来的N行按照前来的次序描述了每一个顾客，每行的格式如下：
A K1 K2…KA B
A表示该顾客拥有的钥匙数，K1...KA表示每个钥匙所对应的猪圈，B表示该顾
客需要购买的猪的数目。
1 ≤ M ≤ 1000
1 ≤ N ≤ 100
Output
仅包含一个整数，即最多能卖出去的猪的数目。
Sample Input
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
Sample Output
7
Solution:
如何构建网络图呢？
我们知道每次一个顾客来买完猪后，我们都可以通过调整猪圈里猪的数量来得到最优解，如何实现调整这个步骤？
我们可以把第一个拥有x猪圈的钥匙的人看做一个中转站，与x猪圈连边，对于之后的每个拥有x猪圈钥匙的人都与这个人连边，边的容量都为inf，就能实现调整猪的行动了
显然的是，要先把每个猪圈与源点连边，容量为猪圈内一开始的猪的数量，再把每个顾客与汇点连边，容量为顾客的需求
完成建图之后，再跑一遍最大流就行了
Code:
#include<queue>
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<algorithm>
#define N 2001
#define inf 1926081700
using namespace std;
int n,m,cnt=1,S,T,head[N*3],dep[N*3];
int fst[N],num[N],vis[N];
struct Edge{int nxt,to,val;}edge[N*3];
void ins(int x,int y,int z){
edge[++cnt].nxt=head[x];
edge[cnt].to=y;edge[cnt].val=z;
head[x]=cnt;
}
namespace Network_Flow{
queue<int> q;
int bfs(){
memset(dep,0,sizeof(dep));
q.push(S);dep[S]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].nxt)
if(edge[i].val&&!dep[edge[i].to]){
dep[edge[i].to]=dep[x]+1;
q.push(edge[i].to);
}
}
if(dep[T]) return 1;
return 0;
}
int dfs(int x,int rest){
if(rest<=0||x==T) return rest;
int flow=0;
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to,v=edge[i].val;
if(dep[y]==dep[x]+1&&v){
int now=dfs(y,min(rest,v));
edge[i].val-=now;
edge[i^1].val+=now;
flow+=now;rest-=now;
if(rest<=0) break;
}
}
return flow;
}
int dinic(){
int maxflow=0;
while(bfs()) maxflow+=dfs(S,inf);
return maxflow;
}
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
n=read(),m=read();
S=1,T=n+m+2;
using namespace Network_Flow;
for(int i=1;i<=n;i++){
int x=read();
ins(S,i+1,x);
ins(i+1,S,0);
}
for(int i=1;i<=m;i++){
int x=read(),tot=0;
memset(vis,0,sizeof(vis));
for(int j=1;j<=x;j++){
int y=read();
if(!fst[y]){
num[++tot]=y+1;
fst[y]=i+n+1;
}else {
if(vis[fst[y]]) continue;
num[++tot]=fst[y];
vis[fst[y]]=1;
}
}
x=read();
ins(i+n+1,T,x);ins(T,i+n+1,0);
for(int j=1;j<=tot;j++){
ins(num[j],i+n+1,inf);
ins(i+n+1,num[j],0);
}
}
printf("%d
",dinic());
return 0;
}