和上一题一样， 也是一个最大权闭合子图。不过建图好麻烦的感觉 写了好久。
源点和原材料连边， 权值为val。 汇点和产品连边， 权值为val。 产品与和它有关系的材料连边， 权值inf。 最后跑一边网络流， 满流的话是没利润的， 输出结果是利润和-最大流。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 20000; 20 int head[maxn*4], s, t, num, q[maxn*10], dis[maxn], used[maxn], cnt1, cnt2, ans1[maxn], ans2[maxn]; 21 map <string, int> vis; 22 struct 23 { 24 int val; 25 string name; 26 }a[maxn]; 27 struct node 28 { 29 int to, nextt, c; 30 }e[maxn*4]; 31 void init() { 32 mem1(head); 33 num = cnt1 = cnt2 = 0; 34 mem(used); 35 vis.clear(); 36 } 37 void add(int u, int v, int c) { 38 e[num].to = v; e[num].nextt = head[u]; e[num].c = c; head[u] = num++; 39 e[num].to = u; e[num].nextt = head[v]; e[num].c = 0; head[v] = num++; 40 } 41 int bfs() { 42 int u, v, st = 0, ed = 0; 43 mem(dis); 44 dis[s] = 1; 45 q[ed++] = s; 46 while(st<ed) { 47 u = q[st++]; 48 for(int i = head[u]; ~i; i = e[i].nextt) { 49 v = e[i].to; 50 if(e[i].c&&!dis[v]) { 51 dis[v] = dis[u]+1; 52 if(v == t) 53 return 1; 54 q[ed++] = v; 55 } 56 } 57 } 58 return 0; 59 } 60 int dfs(int u, int limit) { 61 if(u == t) 62 return limit; 63 int cost = 0; 64 for(int i = head[u]; ~i; i = e[i].nextt) { 65 int v = e[i].to; 66 if(e[i].c&&dis[u] == dis[v]-1) { 67 int tmp = dfs(v, min(limit-cost, e[i].c)); 68 if(tmp>0) { 69 e[i].c -= tmp; 70 e[i^1].c += tmp; 71 cost += tmp; 72 if(cost == limit) 73 break; 74 } else { 75 dis[v] = -1; 76 } 77 } 78 } 79 return cost; 80 } 81 int dinic() { 82 int ans = 0; 83 while(bfs()) { 84 ans += dfs(s, inf); 85 } 86 return ans; 87 } 88 void dfs(int u) { 89 used[u] = 1; 90 for(int i = head[u]; ~i; i = e[i].nextt) { 91 int v = e[i].to; 92 if(e[i].c&&!used[v]) { 93 dfs(v); 94 } 95 } 96 } 97 int main() 98 { 99 int T, n, q, val, x; 100 cin>>T; 101 while(T--) { 102 cin>>n; 103 init(); 104 s = 0; 105 int i, sum = 0; 106 for(i = 1; i<=n; i++) { 107 cin>>a[i].name>>a[i].val; 108 vis[a[i].name] = i; 109 add(s, i, a[i].val); 110 } 111 cin>>q; 112 t = n+q+1; 113 string str; 114 while(q--) { 115 cin>>a[i].name>>a[i].val>>x; 116 sum += a[i].val; 117 add(i, t, a[i].val); 118 while(x--) { 119 cin>>str; 120 add(vis[str], i, inf); 121 } 122 i++; 123 } 124 int ans = sum - dinic(); 125 dfs(0); 126 for(int i = head[s]; ~i; i = e[i].nextt) { 127 int v = e[i].to; 128 if(!used[v]) { 129 ans1[cnt1++] = v; 130 } 131 } 132 for(int i = head[t]; ~i; i = e[i].nextt) { 133 int v = e[i].to; 134 if(!used[v]) { 135 ans2[cnt2++] = v; 136 } 137 } 138 cout<<ans<<endl; 139 cout<<cnt2<<endl; 140 for(int i = 0; i<cnt2; i++) { 141 cout<<a[ans2[i]].name<<endl; 142 } 143 cout<<cnt1<<endl; 144 for(int i = 0; i<cnt1; i++) 145 cout<<a[ans1[i]].name<<endl; 146 } 147 }