网络流24题 太空飞行计划问题

题目传送门

这道题不是好久之前做的了
填一下网络流24题的坑

---

本质上是个最大权闭合图问题的模板

在源点\(S\)和每个实验之间连一条边权为实验利益的边
在每个实验和它需要的仪器之间连一条边权为\(+\infty\)的边
在仪器和汇点\(t\)之间连一条边权为仪器花费的边

然后跑最小割就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long
#define inf 0x7fffffff
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
        k = k * 10 + c - 48, c = getchar();
    return k * f;
}
struct zzz {
    int t, nex, len;
}e[100010 << 1]; int head[1010], tot = 1;
void add(int x, int y, int z) {
    e[++tot].t = y;
    e[tot].len = z;
    e[tot].nex = head[x];
    head[x] = tot;
}
int s, t; int vis[110];
bool bfs() {
    memset(vis, 0, sizeof(vis));
    queue <int> q; q.push(s); vis[s] = 1;
    while(!q.empty()) {
        int k = q.front(); q.pop();
        for(int i = head[k]; i; i = e[i].nex) {
            if(!vis[e[i].t] && e[i].len) {
                vis[e[i].t] = vis[k] + 1;
                if(e[i].t == t) return 1;
                q.push(e[i].t);
            }
        }
    }
    return vis[t];
}
int dfs(int x, int flow) {
    if(!flow || x == t) return flow;
    int rest = 0, fl;
    for(int i = head[x]; i; i = e[i].nex) {
        if(vis[e[i].t] == vis[x] + 1 && (fl = dfs(e[i].t, min(flow - rest, e[i].len)))) {
            rest += fl; e[i].len -= fl; e[i^1].len += fl;
            if(rest == flow) return rest;
        }
    }
    if(rest < flow) vis[x] = 0;
    return rest;
}
int dinic() {
    int ans = 0;
    while(bfs()) ans += dfs(s, inf);
    return ans;
}
int main() {
    //freopen("1.txt", "w", stdout);
    int m = read(), n = read(); s = m+n+1, t = m+n+2;
    int sum = 0;
    for(int i = 1; i <= m; ++i) {
        int x = read(); sum += x;
        add(s, i, x), add(i, s, 0);

        char tools[10000];
        memset(tools, 0, sizeof tools);
        cin.getline(tools, 10000);
        int ulen=0,tool;
        while(sscanf(tools+ulen, "%d", &tool) == 1) {
            add(i, tool+m, inf); add(tool+m, i, 0);
            if(tool == 0) ulen++;
            else while(tool)
                tool /= 10, ulen++;
            ulen++;
        }
    }
    for(int i = 1; i <= n; ++i) {
        int x = read();
        add(i+m, t, x); add(t, i+m, 0);
    }
    sum -= dinic();
    for(int i = 1; i <= m; ++i)
        if(vis[i]) cout << i << ' ';
    cout << endl;
    for(int i = 1; i <= n; ++i)
        if(vis[i+m]) cout << i << ' ';
    cout << endl;
    cout << sum;
    return 0;
}