题意：
有 M 个猪圈（M ≤ 1000），每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。
依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，从中买若干头猪。
每个顾客分别都有他能够买的数量的上限。
每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。
问总共最多能卖出多少头猪。
第一行是两个整数：M和N（1≤M≤1000，1≤N≤100）
M是猪圈的数目，N是顾客的数目
第二行是M个整数，为每个猪圈中初始猪的数目，范围是[0，1000]
第三行接下来有N行，每行第一个数A代表第几个顾客会依次打开A个猪圈，
然后跟着有A个数，代表顾客打开的是哪个猪圈，最后有一个数代表这个顾客可以买多少只猪
现在求怎么一种方法，使所有顾客买的猪的总数最大
解题思路：将顾客看作节点,新建一个源点与汇点
源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目,当然这样会有重边要考虑
顾客j紧跟在顾客i之后打开某个猪圈，则边<i,j>的权是无限大
每个顾客和汇点之间连边，边的权是顾客所希望购买的猪的数目
当然首先想到的图不可能是一个这样的图，我们首先构图，是让源点指向所有的猪圈，权值为猪圈的个数
然后猪圈指向第一个打开它的顾客，在前面顾客指向下一个顾客，权值为无限大，这样下去，顾客再指向汇点
权值为顾客要买的猪的个数
参考对图的简化规则：
规律 1. 如果几个节点的流量的来源完全相同，则可以把它们合并成一个。
规律 2. 如果几个节点的流量的去向完全相同，则可以把它们合并成一个。
规律 3. 如果从点 u 到点 v 有一条容量为 +∞ 的边，并且 u 是 v 的唯一流量来源，或者 v 是 u 的唯一流量去向，则可以把 u 和 v 合并成一个节点。
/*
sap
Memory 216K
Time 0MS
*/#include <iostream>
using namespace std;
#define MAXV 110
#define MAXM 1010
#define INF INT_MAX
#define min(a,b) (a>b?b:a)
int sink,source,res[MAXV][MAXV],n;
int pre[MAXV],dis[MAXV],gap[MAXV],maxflow,cur[MAXV];
void sap(){
int s=source,t=sink;
memset(cur,0,sizeof(cur));
memset(dis,0,sizeof(dis));
memset(gap,0,sizeof(gap));
int u=pre[s]=s,aug=INF,v;
maxflow=0;
gap[source]=n;
while(dis[s]<n){
loop:
for(v=cur[u];v<n;v++)
if(res[u][v] && dis[u]==dis[v]+1){
cur[u]=v;
aug=min(aug,res[u][v]);
pre[v]=u;
u=v;
if(v==t){
maxflow+=aug;
for(u=pre[u];v!=s;v=u,u=pre[u]) res[u][v]-=aug,res[v][u]+=aug;
aug=INF;
}
goto loop;
}
int mind=n;
for(v=0;v<n;v++)
if(res[u][v]&&(mind>dis[v])){
cur[u]=v;
mind=dis[v];
}
if((--gap[dis[u]])==0) break;
gap[dis[u]=mind+1]++;
u=pre[u];
}
}
int main(){
int i,m,cnt,num,j;
int pig[MAXM];
int k[MAXM];
while(~scanf("%d%d",&m,&n)){
memset(k,0,sizeof(k));
memset(res,0,sizeof(res));
for(i=1;i<=m;i++) scanf("%d",&pig[i]);
source=0,sink=n+1;
for(i=1;i<=n;i++){
scanf("%d",&cnt);
for(j=1;j<=cnt;j++){
scanf("%d",&num);
if(!k[num]) res[source][i]+=pig[num];
else res[k[num]][i]=INF;
k[num]=i;
}
scanf("%d",&num);
res[i][sink]=num;
}
n=sink+1;
sap();
printf("%d\n",maxflow);
}
return 0;
}
/*
dinic
Memory 224K
Time 32MS
*/
#include <iostream>
#include <queue>
#define MAXM 1005
#define MAXV 105
#define INF INT_MAX
using namespace std;
int res[MAXV][MAXV]; //cap为最大容量,f为流量
int dis[MAXV]; //表示多少层
int n,source,sink,maxflow; //s为源点,t为汇点
int min(int a,int b){return a > b ? b : a;}
int bfs(){
int k;
queue<int> q;
memset(dis,-1,sizeof(dis));
dis[sink]=0;
q.push(sink);
while(!q.empty()){
k=q.front();
q.pop();
for(int i = 0; i <=n+1; i++){
if(dis[i]==-1 && res[i][k]){
dis[i] = dis[k] + 1;
q.push(i);
}
}
if(k==source) return 1;
}
return 0;
}
int dfs(int cur,int cp){
if(cur==sink) return cp;
int tmp=cp,t;
for(int i=0;i<=n+1 && tmp;i++) {
if(dis[i]+1==dis[cur] && res[cur][i]){
t=dfs(i,min(res[cur][i],tmp));
res[cur][i]-=t;
res[i][cur]+=t;
tmp-=t;
}
}
return cp-tmp;
}
void dinic(){
maxflow=0;
while(bfs()){
maxflow+=dfs(source,INF);
}
}
int main(){
int i,m,cnt,num,j;
int pig[MAXM];
int k[MAXM];
while(~scanf("%d%d",&m,&n)){
memset(k,0,sizeof(k));
memset(res,0,sizeof(res));
for(i=1;i<=m;i++) scanf("%d",&pig[i]);
source=0,sink=n+1;
for(i=1;i<=n;i++){
scanf("%d",&cnt);
for(j=1;j<=cnt;j++){
scanf("%d",&num);
if(!k[num]) res[source][i]+=pig[num];
else res[k[num]][i]=INF;
k[num]=i;
}
scanf("%d",&num);
res[i][sink]=num;
}
n=sink+1;
dinic();
printf("%d\n",maxflow);
}
return 0