zoj2071:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2071
题意：题意一些零件，每一个零件会有一个花费，然后用这些的零件可以生产一些产品，产品可以卖出一些钱，现在问你这些零件可以专区的额最大花费。
题解：零件和源点建立一边，容量为零件的费用，然后产品和汇点建立边，容量为产品的价值，然后零件盒产品之间建立相应的边，容量为INF，然后跑网络流，如果某产品和汇点之间的满流，说明，生产这样的产品赚取的费用是0，所以这样的产品是可以不成产的，所以，只要统计没有满流的安歇边就可以了。同时，这里的零件是可以购买多次的，也就是说，你可以买两个以上的相同零件用于生产不同的产品。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<map>
#define INF 100000000
using namespace std;
const int N=;
const int M=;
struct Node{
int v;
int f;
int next;
}edge[M];
int n,m,u,v,cnt,sx,ex;
int head[N],pre[N];
int ans[N],top;
struct Edge{
char str[];
int t;
int val;
char ss[][];
}num[N];
void init(){
cnt=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w){
edge[cnt].v=v;
edge[cnt].f=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool BFS(){
memset(pre,,sizeof(pre));
pre[sx]=;
queue<int>Q;
Q.push(sx);
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=head[d];i!=-;i=edge[i].next ){
if(edge[i].f&&!pre[edge[i].v]){
pre[edge[i].v]=pre[d]+;
Q.push(edge[i].v);
}
}
}
return pre[ex]>;
}
int dinic(int flow,int ps){
int f=flow;
if(ps==ex)return f;
for(int i=head[ps];i!=-;i=edge[i].next){
if(edge[i].f&&pre[edge[i].v]==pre[ps]+){
int a=edge[i].f;
int t=dinic(min(a,flow),edge[i].v);
edge[i].f-=t;
edge[i^].f+=t;
flow-=t;
if(flow<=)break;
} }
if(f-flow<=)pre[ps]=-;
return f-flow;
}
int solve(){
int sum=;
while(BFS())
sum+=dinic(INF,sx);
return sum;
}
char temp[];
int main() {
int T,k,sum1,sum2,t1,tt=;
scanf("%d",&T);
while(T--) {
if(tt>)puts("");
tt=;
scanf("%d",&n);
init();
map<string,int>mp1;
for(int i=;i<=n;i++){
scanf("%s%d",temp,&t1);
mp1[temp]=i;
add(,i,t1);
}
scanf("%d",&m);sum1=;
for(int i=;i<=m;i++){
scanf("%s%d%d",num[i].str,&t1,&num[i].t);
mp1[num[i].str]=i+n;
num[i].val=t1;
sum1+=t1;
add(i+n,n+m+,t1);
for(int j=;j<=num[i].t;j++){
scanf("%s",num[i].ss[j]);
add(mp1[num[i].ss[j]],i+n,INF);
}
}
sx=;ex=n+m+;top=;
printf("%d\n",sum1-solve());
for(int i=n+;i<=n+m;i++){
for(int j=head[i];j!=-;j=edge[j].next){
if(edge[j].f>&&edge[j].v==n+m+){
ans[++top]=i-n;
}
}
}
printf("%d\n",top);sum2=;
for(int i=;i<=top;i++){
printf("%s\n",num[ans[i]].str);
sum2+=num[ans[i]].t;
}
printf("%d\n",sum2);
for(int i=;i<=top;i++){
int ttt=num[ans[i]].t;
for(int j=;j<=ttt;j++)
printf("%s\n",num[ans[i]].ss[j]);
}
}
return ;
}