题意： 有 M 个猪圈，每个猪圈里初始时有若干头猪，一开始所有猪圈都是关闭的，依次来了 N 个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪，
每个顾客分别都有他能够买的数量的上限，每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。
分析：此题建图关键在于合并猪圈
建图：
对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量
如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加，
对于每个猪圈，假设有 n 个顾客打开过它，则对所有整数 i ∈ [1, n)，从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边，容量为INF
从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限
#include<stdio.h> #include<string.h> #define INF 0x1f1f1f1f #define clr(x)memset(x,0,sizeof(x)) #define min(a,b)(a)<(b)?(a):(b) int gap[105]; int dis[105]; int c[105][105]; void init(int s,int u,int n) {int v,x,front=0,rear=0;int q[105];clr(gap);memset(dis,0xff,sizeof(dis));q[rear++]=u;dis[u]=0;while(front<rear){x=q[front++];gap[dis[x]]++;for(v=0;v<=n;v++)if(dis[v]==-1&&c[v][x]>0){dis[v]=dis[x]+1;q[rear++]=v;}} } int sap(int s,int u,int n) {init(s,u,n);int flag,flow=0,top=s,i,j,k;int pre[105];int low[105];while(dis[s]<=n){flag=0;low[s]=INF;for(i=0;i<=n;i++)if(c[top][i]>0&&dis[top]==dis[i]+1&&dis[i]>=0){flag=1;break;}if(flag){low[i]=c[top][i];low[i]=min(low[i],low[top]);pre[i]=top;top=i;if(top==u){flow+=low[u];j=top;while(j!=s){k=pre[j];c[k][j]-=low[u];c[j][k]+=low[u];j=k;}top=s;clr(low);}}else{int dmin=n;for(j=0;j<=n;j++)if(c[top][j]>0&&dis[j]+1<dmin&&dis[j]>=0)dmin=dis[j]+1;gap[dis[top]]--;if(gap[dis[top]]==0)break;gap[dmin]++;dis[top]=dmin;if(top!=s)top=pre[top];}}return flow; } int pig[1002]; int p_v[1002]; int main() {int m,n,i,t,p;while(scanf("%d%d",&m,&n)!=EOF){clr(p_v);clr(c);for(i=1;i<=m;i++)scanf("%d",&pig[i]);for(i=1;i<=n;i++){scanf("%d",&t);while(t--){scanf("%d",&p);if(!p_v[p])c[0][i]+=pig[p];else c[p_v[p]][i]=INF;p_v[p]=i;}scanf("%d",&p);c[i][n+1]=p;}printf("%d\n",sap(0,n+1,n+1));}return 0; }