这题套路好深......没想渠。
题意：给你若干个设备，若干个任务。
每个任务需要若干设备，设备可重复利用。
完成任务有钱，买设备要钱。
问最大总收益(可以什么任务都不做)。
解：最大权闭合子图。
对于一个有向图，如果选择了一个点，那么就要选择它的所有后继节点。求最大权值和。
建立s，t，记所有正权值和为sum。
s向所有权值为正的点连边，流量为权值。
所有权值为负的点向t连边，流量为权值的绝对值。
对于所有边，建立流量INF的边。
答案即为sum - 最小割。
证明：
你割的边显然只能与s或t相连。
如果割了s -> a，表示不选a。
如果割了b -> t，表示选b。
那么如果你选了一个点c，那么就没割，那么c的所有后继节点肯定都割了。
大概就是这样...意会一下吧。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 #include <iostream> 6 #include <string> 7 8 const int N = 107, M = 1000010, INF = 0x3f3f3f3f; 9 10 struct Edge { 11 int nex, v, c; 12 }edge[M << 1]; int top = 1; 13 14 int e[N], d[N], use[N]; 15 std::queue<int> Q; 16 std::string str; 17 18 inline void add(int x, int y, int z) { 19 top++; 20 edge[top].v = y; 21 edge[top].c = z; 22 edge[top].nex = e[x]; 23 e[x] = top; 24 25 top++; 26 edge[top].v = x; 27 edge[top].c = 0; 28 edge[top].nex = e[y]; 29 e[y] = top; 30 return; 31 } 32 33 inline bool BFS(int s, int t) { 34 memset(d, 0, sizeof(d)); 35 d[s] = 1; 36 Q.push(s); 37 while(!Q.empty()) { 38 int x = Q.front(); 39 Q.pop(); 40 for(int i = e[x]; i; i = edge[i].nex) { 41 int y = edge[i].v; 42 if(!edge[i].c || d[y]) { 43 continue; 44 } 45 d[y] = d[x] + 1; 46 Q.push(y); 47 } 48 } 49 return d[t]; 50 } 51 52 int DFS(int x, int t, int maxF) { 53 if(x == t) { 54 return maxF; 55 } 56 int ans = 0; 57 for(int i = e[x]; i; i = edge[i].nex) { 58 int y = edge[i].v; 59 if(!edge[i].c || d[x] + 1 != d[y]) { 60 continue; 61 } 62 int temp = DFS(y, t, std::min(edge[i].c, maxF - ans)); 63 if(!temp) { 64 d[y] = INF; 65 } 66 ans += temp; 67 edge[i].c -= temp; 68 edge[i ^ 1].c += temp; 69 if(ans == maxF) { 70 break; 71 } 72 } 73 return ans; 74 } 75 76 inline int solve(int s, int t) { 77 int ans = 0; 78 while(BFS(s, t)) { 79 ans += DFS(s, t, INF); 80 } 81 return ans; 82 } 83 84 inline void read(int *a) { 85 getline(std::cin, str); 86 a[0] = 0; 87 int len = str.size(); 88 int f = 0; 89 for(int i = 0; i < len; i++) { 90 if(str[i] < '0' || str[i] > '9') { 91 f = 0; 92 } 93 else { 94 if(!f) { 95 f = 1; 96 a[++a[0]] = str[i] - '0'; 97 } 98 else { 99 (a[a[0]] *= 10) += str[i] - '0'; 100 } 101 } 102 } 103 return; 104 } 105 106 int main() { 107 int m, n, sum = 0; 108 scanf("%d%d", &m, &n); 109 int s = m + n + 1, t = n + m + 2; 110 for(int i = 1, x; i <= m; i++) { 111 scanf("%d", &x); 112 add(s, i, x); 113 read(use); 114 for(int j = 1; j <= use[0]; j++) { 115 add(i, m + use[j], INF); 116 } 117 sum += x; 118 } 119 for(int i = 1, x; i <= n; i++) { 120 scanf("%d", &x); 121 add(m + i, t, x); 122 } 123 124 int ans = solve(s, t); 125 for(int i = 1; i <= m; i++) { 126 if(d[i]) { 127 printf("%d ", i); 128 } 129 } 130 puts(""); 131 for(int i = 1; i <= n; i++) { 132 if(d[i + m]) { 133 printf("%d ", i); 134 } 135 } 136 printf(" %d", sum - ans); 137 return 0; 138 }