前言

第二道紫，开心QWQ

题目大意

有一个航天中心，有 $m$ 个实验可以做。每做一个实验之前需要购买给出的清单上的仪器，告诉你它的价钱。但如果之前的实验已经买过了就不用再买。但是每能做一个实验就可以得到这个实验的赞助，问净收益是多少？

思路

首先本题是网络流，然后能确定没有源点和汇点，所以建超级源点汇点。之后肯定让源点跟每一个实验连一条能得到的赞助为边权的有向边。但之后就卡住了。我们本题是既要有权值也要有费用的，这可不好确定。我们让每一个实验和需要的仪器清单连一条边权为 $+\infty$ 的边。因为如果希望买到所有仪器，是不需要分配的，完全可以用全部的钱去试一下能不能买到，之后的剩余再去买下一条边。之后再把仪器和汇点连一条仪器花费的边。之后跑一次最大流。

但是上面的做法看起来明显不对，我们要用所有实验的总和减去这个最大流的值。这是一个极为巧妙的点。因为如果买不起，那么必然这个实验的所有钱都会流到汇点，也就是说全汇过去都买不起。但如果有的还有剩余，那就是买完了所有仪器的剩余。用这个实验的价钱减去就行了。

还可能会说那万一正好全买到了呢？想想，正好买完的收益是 $0$，买下来完全不会赚。所以不会影响结果。但是该买的还是要买。之后可能会说那我跑最大流我汇过去了这么些那我万一买不起呢？由于只有一条边往 $t$ 连，就跟上一个笔记 P2763 试题库问题 一样，用了阀门 技巧，如果这个和另外一个凑了一个，那么这个假设凑不出来就都流出去了，相当于没凑，那么在最后要减掉这个凑了一些的值，所以就算正好另外一个补全了，还是有一部分的值要被减掉，然后一个点剩了一些就还是都流过去了。可以画个图理解一下。

路径可以扫一遍 dinic 的 bfs 分的图，如果分过就说明有路径可以到，没有全部流完。并且流到了就说明全买到了。

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef long long ll;
const ll MAXN = 1000 + 5;
const ll MAXM = 100 + 5;
const ll INF = ll(1e30);
ll n, m, s = 0, t = MAXN - 1;
struct edge {
    ll to, weight, nxt;
} e[MAXM * 10];
ll head[MAXN], tot = 1;

void add(ll u, ll v, ll w) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    e[tot].weight = w;
    head[u] = tot;
}

ll dep[MAXN], arc[MAXM * 2], a[MAXN];

bool bfs() {
    for (int i = 0; i < MAXN; ++i) {
        dep[i] = -1;
    }
    queue<ll> q;
    q.push(s);
    dep[s] = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll i = head[u]; i; i = e[i].nxt) {
            ll v = e[i].to, w = e[i].weight;
            if (dep[v] == -1 && w) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    if (dep[t] != -1) {
        return true;
    }
    return false;
}

ll dfs(ll u, ll inflow) {
    if (u == t) {
        return inflow;
    }
    ll outflow = 0;
    for (ll i = arc[u]; i && inflow; i = e[i].nxt) {
        arc[u] = e[i].to;
        if (dep[e[i].to] == dep[u] + 1 && e[i].weight) {
            ll v = e[i].to, W = dfs(v, min(e[i].weight, inflow));
            if (W == 0) {
                dep[v] = -INF;
            }
            e[i].weight -= W;
            e[i ^ 1].weight += W;
            outflow += W;
            inflow -= W;
        }
    }
    return outflow;
}

ll dinic() {
    ll ans = 0;
    while (bfs()) {
        for (int i = 0; i <= m + n; ++i) {
            arc[i] = head[i];
        }
        arc[t] = head[t];
        ans += dfs(s, INF);
    }
    return ans;
}

ll v[MAXN][MAXN], sz[MAXN];

int main() {
    scanf("%lld%lld", &m, &n);
    ll sum = 0;
    for (int i = 1; i <= m; ++i) {
        ll c;
        scanf("%lld", &c);
        sum += c;
        add(s, i, c);
        add(i, s, 0);
        char tools[10000];
        memset(tools, 0, sizeof tools);
        cin.getline(tools, 10000);
        int u_len = 0, tool;
        while (sscanf(tools + u_len, "%d", &tool) == 1) {
            v[i][++sz[i]] = tool;
            if (tool == 0)
                u_len++;
            else {
                while (tool) {
                    tool /= 10;
                    u_len++;
                }
            }
            u_len++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        add(i + m, t, a[i]);
        add(t, i + m, 0);
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= sz[i]; ++j) {
            add(i, v[i][j] + m, INF);
            add(v[i][j] + m, i, 0);
        }
    }
    ll ans = dinic();
    for (int i = 1; i <= m; ++i) {
        if (dep[i] != -1) {
            printf("%d ", i);
        }
    }
    printf("\n");
    for (int i = 1; i <= n; ++i) {
        if (dep[i + m] != -1) {
            printf("%d ", i);
        }
    }
    printf("\n%lld", sum - ans);
    return 0;
}

总结

在碰到这些又有费用还有权值在一个图上然后有前置关系的可以尝试将费用先算出来，之后在通过类似容斥的方法消掉费用，留下最终答案。