太空飞行计划问题

最大权闭合子图：等于正边权 - 最大流（最小割）
我的理解
最大收益就是要求最小损失，那么用最小割模型（别问我是怎么想到的）
S向实验连边，表示割掉这条边，把实验割给T会有损失
T向配置连边，表示割掉这条边，把配置割给S会有损失
跑出的最小割（最大流）就是损失

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# 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("
");
    for(RG int i = 1; i <= n; i++)
        if(vis[i + m]) printf("%d ", i);
    printf("
%d
", tot - ans);
    return 0;
}