最大权闭合子图：等于正边权 - 最大流（最小割）
我的理解 最大收益就是要求最小损失，那么用最小割模型（别问我是怎么想到的） S向实验连边，表示割掉这条边，把实验割给T会有损失 T向配置连边，表示割掉这条边，把配置割给S会有损失 跑出的最小割（最大流）就是损失# include# include # include # include # define ll long long# define RG register# define IL inline# define mem(a, b) memset(a, b, sizeof(a))# define Max(a, b) (((a) > (b)) ? (a) : (b))# define Min(a, b) (((a) < (b)) ? (a) : (b))using namespace std;const int MAXN = 1001, INF = 2147483647;int n, m, map[MAXN][MAXN], ans, level[MAXN], Q[MAXN * MAXN], tot, vis[MAXN];char s[MAXN];IL bool Bfs(RG int S, RG int T){ mem(level, 0); mem(vis, 0); RG int head = 0, tail = 0; level[S] = 1; Q[0] = S; while(head <= tail){ RG int u = Q[head++]; if(u == T) return 1; for(RG int v = 1; v <= T; v++) if(!level[v] && map[u][v]){ level[v] = level[u] + 1; vis[v] = 1; Q[++tail] = v; } } return 0;}IL int Dfs(RG int u, RG int T, RG int maxf){ if(u == T) return maxf; RG int ret = 0; for(RG int v = 1; v <= T; v++) if(level[v] == level[u] + 1 && map[u][v]){ RG int f = Dfs(v, T, Min(maxf - ret, map[u][v])); map[u][v] -= f; map[v][u] += f; ret += f; if(ret == maxf) break; } return ret;}int main(){ scanf("%d%d", &m, &n); for(RG int i = 1; i <= m; i++){ RG int f, v, j = 0, x; scanf("%d", &f); map[0][i] = f; tot += f; mem(s, 0); cin.getline(s, 10000); while(sscanf(s + j, "%d", &x)==1){ if(!x) j++; else map[i][m + x] = INF; while(x) x /= 10, j++; j++; } } for(RG int i = 1; i <= n; i++) scanf("%d", &map[m + i][m + n + 1]); while(Bfs(0, m + n + 1)) ans += Dfs(0, m + n + 1, INF); for(RG int i = 1; i <= m; i++) if(vis[i]) printf("%d ", i); printf("\n"); for(RG int i = 1; i <= n; i++) if(vis[i + m]) printf("%d ", i); printf("\n%d\n", tot - ans); return 0;}