这题套路好深......没想渠。
题意：给你若干个设备，若干个任务。
每个任务需要若干设备，设备可重复利用。
完成任务有钱，买设备要钱。
问最大总收益(可以什么任务都不做)。
解：最大权闭合子图。
对于一个有向图，如果选择了一个点，那么就要选择它的所有后继节点。求最大权值和。
建立s，t，记所有正权值和为sum。
s向所有权值为正的点连边，流量为权值。
所有权值为负的点向t连边，流量为权值的绝对值。
对于所有边，建立流量INF的边。
答案即为sum - 最小割。
证明：
你割的边显然只能与s或t相连。
如果割了s -> a，表示不选a。
如果割了b -> t，表示选b。
那么如果你选了一个点c，那么就没割，那么c的所有后继节点肯定都割了。
大概就是这样...意会一下吧。
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string> const int N = , M = , INF = 0x3f3f3f3f; struct Edge {
int nex, v, c;
}edge[M << ]; int top = ; int e[N], d[N], use[N];
std::queue<int> Q;
std::string str; inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].nex = e[y];
e[y] = top;
return;
} inline bool BFS(int s, int t) {
memset(d, , sizeof(d));
d[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[y]) {
continue;
}
d[y] = d[x] + ;
Q.push(y);
}
}
return d[t];
} int DFS(int x, int t, int maxF) {
if(x == t) {
return maxF;
}
int ans = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[x] + != d[y]) {
continue;
}
int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
if(!temp) {
d[y] = INF;
}
ans += temp;
edge[i].c -= temp;
edge[i ^ ].c += temp;
if(ans == maxF) {
break;
}
}
return ans;
} inline int solve(int s, int t) {
int ans = ;
while(BFS(s, t)) {
ans += DFS(s, t, INF);
}
return ans;
} inline void read(int *a) {
getline(std::cin, str);
a[] = ;
int len = str.size();
int f = ;
for(int i = ; i < len; i++) {
if(str[i] < '' || str[i] > '') {
f = ;
}
else {
if(!f) {
f = ;
a[++a[]] = str[i] - '';
}
else {
(a[a[]] *= ) += str[i] - '';
}
}
}
return;
} int main() {
int m, n, sum = ;
scanf("%d%d", &m, &n);
int s = m + n + , t = n + m + ;
for(int i = , x; i <= m; i++) {
scanf("%d", &x);
add(s, i, x);
read(use);
for(int j = ; j <= use[]; j++) {
add(i, m + use[j], INF);
}
sum += x;
}
for(int i = , x; i <= n; i++) {
scanf("%d", &x);
add(m + i, t, x);
} int ans = solve(s, t);
for(int i = ; i <= m; i++) {
if(d[i]) {
printf("%d ", i);
}
}
puts("");
for(int i = ; i <= n; i++) {
if(d[i + m]) {
printf("%d ", i);
}
}
printf("\n%d", sum - ans);
return ;
}
AC代码