【题目大意】
有M个项目和N个员工。做项目i可以获得Ai元，但是必须雇用若干个指定的员工。雇用员工j需要花费Bj元，且一旦雇用，员工j可以参加多个项目的开发。问经过合理的项目取舍，最多能挣多少钱。（1 <= M, N <= 100）
蕴含式最大获利问题。。建出最大权闭合子图，答案为sum(a[i])-最小割
1 //#include<bits/stdc++.h> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<iostream> 7 #define inc(i,l,r) for(int i=l;i<=r;i++) 8 #define dec(i,l,r) for(int i=l;i>=r;i--) 9 #define link(x) for(edge *j=h[x];j;j=j->next) 10 #define mem(a) memset(a,0,sizeof(a)) 11 #define inf 1e9 12 #define ll long long 13 #define succ(x) (1<<x) 14 #define NM 300 15 #define nm 100000 16 using namespace std; 17 int read(){ 18 int x=0,f=1;char ch=getchar(); 19 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} 20 while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); 21 return x*f; 22 } 23 struct edge{ 24 int t,v; 25 edge *next,*rev; 26 }e[nm],*h[NM],*p; 27 void _add(int x,int y,int v){ 28 p->t=y;p->v=v;p->next=h[x];h[x]=p;p++; 29 } 30 void add(int x,int y,int v){ 31 _add(x,y,v);_add(y,x,0); 32 h[x]->rev=h[y];h[y]->rev=h[x]; 33 } 34 int n,m,_t,d[NM],T,_x,s; 35 bool v[NM]; 36 queue<int >q; 37 int bfs(){ 38 mem(d);mem(v); 39 v[0]++;d[0]++;q.push(0); 40 while(!q.empty()){ 41 int t=q.front();q.pop(); 42 link(t) 43 if(j->v&&!v[j->t]) 44 v[j->t]++,q.push(j->t),d[j->t]=d[t]+1; 45 } 46 return d[n]; 47 } 48 int dfs(int x,int k){ 49 int _a; 50 if(x==n)return k; 51 link(x) 52 if(j->v&&d[j->t]==d[x]+1&&(_a=dfs(j->t,min(j->v,k)))){ 53 j->v-=_a;j->rev->v+=_a;return _a; 54 } 55 return 0; 56 } 57 int main(){ 58 T=read(); 59 while(T--){ 60 p=e;mem(h);s=0; 61 n=read();m=read(); 62 inc(i,1,n){ 63 _x=read();s+=_x; 64 add(0,i,_x); 65 } 66 inc(i,1,m)add(i+n,n+m+1,read()); 67 inc(i,1,n){ 68 _x=read(); 69 inc(j,1,_x) 70 add(i,n+1+read(),inf); 71 } 72 n=n+m+1; 73 while(bfs()) 74 if(_t=dfs(0,inf))s-=_t; 75 printf("%d ",s); 76 } 77 return 0; 78 }