这道题应该都能想到朴素的有n*m+个点的建图方案吧，呵呵，显然是不行的。
那么怎么办？
其实我们可以这样想：一个人能买到的猪有两个来源：
①来自自己第一次打开的猪圈
②来自之前别人打开的猪圈
想到了这个实质，见图就简单了！
我们设一个超级源点S，和超级汇点T，对于每一个人，从S向他连一条容量为K的边（K是由这个人第一次打开的猪圈的初始猪的个数之和），然后对于一个人A，他打开了P猪圈，
且P猪圈之前被B打开过，则从B向A连一条容量为INF的边，最后，对于每一个人，都向T连一条容量为lim[i]（表示每个人的购买猪的上限）的边，跑在最大流就行！
代码：
View Code
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 #define N 2010 6 #define M 200100 7 #define INF 100000000 8 using namespace std; 9 int head[N],next[M],to[M],len[M],cnt,S,T,n,m,layer[N],q[M<<4]; 10 int cus[N],ini[N],num[N],key[N][N],lim[N],ww[N]; 11 inline void add(int u,int v,int w) 12 { 13 to[cnt]=v; len[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 14 to[cnt]=u; len[cnt]=0; next[cnt]=head[v]; head[v]=cnt++; 15 } 16 void read() 17 { 18 memset(cus,0,sizeof cus); 19 memset(ww,0,sizeof ww); 20 memset(head,-1,sizeof head); 21 cnt=0; 22 S=0; T=n+1; 23 for(int i=1;i<=m;i++) scanf("%d",&ini[i]); 24 for(int i=1;i<=n;i++) 25 { 26 scanf("%d",&num[i]); 27 for(int j=1;j<=num[i];j++) 28 { 29 scanf("%d",&key[i][j]); 30 //cus[i]表示上一次开启i猪圈的人的编号 31 if(cus[key[i][j]]==0)//i是第一个开key[i][j]猪圈的人 32 { 33 ww[i]+=ini[key[i][j]]; 34 cus[key[i][j]]=i;//更新 35 } 36 else 37 { 38 add(cus[key[i][j]],i,INF); 39 cus[key[i][j]]=i; 40 } 41 } 42 scanf("%d",&lim[i]); 43 } 44 for(int i=1;i<=n;i++) add(S,i,ww[i]),add(i,T,lim[i]); 45 } 46 bool bfs() 47 { 48 memset(layer,-1,sizeof layer); 49 int h=1,t=2,sta; 50 q[1]=S; layer[S]=0; 51 while(h<t) 52 { 53 sta=q[h++]; 54 for(int i=head[sta];~i;i=next[i]) 55 if(len[i]>0&&layer[to[i]]<0) 56 { 57 layer[to[i]]=layer[sta]+1; 58 q[t++]=to[i]; 59 } 60 } 61 return layer[T]!=-1; 62 } 63 int find(int u,int cur_flow) 64 { 65 if(u==T) return cur_flow; 66 int result=0,tmp; 67 for(int i=head[u];~i&&result<cur_flow;i=next[i]) 68 if(len[i]>0&&layer[to[i]]==layer[u]+1) 69 { 70 tmp=find(to[i],min(cur_flow-result,len[i])); 71 len[i]-=tmp; len[i^1]+=tmp; result+=tmp; 72 } 73 if(!result) layer[u]=-1; 74 return result; 75 } 76 int dinic() 77 { 78 int ans=0; 79 while(bfs()) ans+=find(S,INF); 80 return ans; 81 } 82 int main() 83 { 84 while(scanf("%d%d",&m,&n)!=EOF) 85 { 86 read(); 87 printf("%d\n",dinic()); 88 } 89 return 0; 90 }