一开始所有猪圈都是关闭的。
依次来了 N 个顾客（N ≤ 100），每个顾客分别会打开指定的几个猪圈，从中买若干头猪。
每个顾客分别都有他能够买的数量的上限。
每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上
【思路】： 此题是网络流，网络流里经典的构图题。将顾客看作除源和漏以外的节点，源和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目，若源和某个节点之间有重边，则将权合并，顾客j紧跟在顾客i之后打开某个猪圈，则边<i,j>的权是+∞，每个顾客和漏之间连边，边的权是顾客所希望购买的猪的数目。然后套模版~
【代码】：
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int f[102][102];
int r[102][102];
bool hash[1002];
int c[102][102];
int m,n,s,t,flow=0;
int pre[1002];
int qq[1002];
int pig[1002];
int tmp;
int di[102];
int dis[102];
int vh[102];
int aug;
bool flag;
int his[102];
void sap()
{
int i,j;
vh[0]=n+2;
for(i=1;i<=n+2;i++) di[i]=1;
i=1;//从S开始搜
aug=0x7fffffff;flow=0;
while(dis[1]<n+2)
{
his[i]=aug;//标记，以便以后返回这个值
flag=false;
for(j=di[i];j<=n+2;j++)
{
if(c[i][j]>0 && dis[j]+1==dis[i])//找到允许弧
{
flag=true;
di[i]=j;//标记当前弧
if(c[i][j]<aug) aug=c[i][j];
pre[j]=i;//记录前驱
i=j;
if(i==t)//找到增广路
{
flow+=aug;
while(i!=1)
{
tmp=i;
i=pre[i];
c[i][tmp]-=aug;
c[tmp][i]+=aug;
}
aug=0x7fffffff;
}
break;//找到允许弧则退出查找
}
}
int minn,j1;
if(flag) continue;
minn=n+1;//没有允许弧了，需要重标号
for(j=1;j<=n+2;j++){
if(c[i][j]>0 && dis[j]<minn) { j1=j;minn=dis[j]; }
}
di[i]=j1;
vh[dis[i]]--;//GAP优化
if(vh[dis[i]]==0) break;
dis[i]=minn+1;
if(i!=1) {
i=pre[i];//返回上一层
aug=his[i];
}
}
}
int main()
{
int i,j;int A,key,qp,buy,w;
while(scanf("%d%d",&m,&n)!=EOF)
{
t=n+2;s=1; flow=0;
memset(c,0,sizeof(c));
memset(dis,0,sizeof(dis));
memset(his,0,sizeof(his));
memset(pre,0,sizeof(pre));
memset(vh,0,sizeof(vh));
memset(hash,false,sizeof(hash));
for(i=1;i<=m;i++)
scanf("%d",&pig[i]);
for(i=2;i<=n+1;i++)
{
scanf("%d",&A);
for(j=0;j<A;j++)
{
scanf("%d",&key);
if(!hash[key])
{
c[s][i]+=pig[key];
hash[key]=true;
qq[key]=i;
}
else
{
qp=qq[key];
c[qp][i]=0x7FFFFFFF;
}
}
scanf("%d",&buy);
c[i][t]+=buy;
}
sap();
printf("%d\n",flow);
}
return 0;
}