题解 CF311E 【Biologist】

· · 题解

最小割

思路

假设我们已经满足了所有的要求，那么最大的收益是每个要求满足后的收益的和那么问题就等价于，我损失哪些要求，可以让我得到最小的损失。在建图的时候用最小割的思维考虑，使得最后的最小割就是最小的损失。

ans=\sum_{i=1}^{m} w_{i} -MinCut

所以边就一定要和价值联系到一起。我们考虑一个要求：

建图

那么我们的建图就可以这么考虑：

如果一个点是1，那么向t连边，价值是转换的价值。如果一个点是0，就从s向它连边，价值也是对应转换的价值。

如果是要0的要求，那么从起点向它连边权为对应收益的边，然后从该要求点向所有的有关节点连正无穷的边。

如果是要1的要求，那么从所有有关节点向它连正无穷的边，然后从该要求节点连向终点，价值为对应的收益。

如果一个要求不满足会扣钱，也就是说满足了是w_{i}的收益，没有满足时-g 的收益。两者差值是w_{i}+g ，所以它来作为边权。

举例

一共3个节点分别是101，2个要求，第一个要求1和2是0，第二个要求2和3是1并且不满足要扣钱，那么可以画出下面的示意图

代码


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010*2;

typedef long long typec;  // 为了方便转换类型
const typec oo = 1e9;

int n, m, s, g, t, head[maxn], nxt[maxn], to[maxn], dep[maxn], cur[maxn], tot = 1;
int W[maxn], A[maxn];
typec w[maxn], sum;

queue<int> Q; 

void add(int x, int y, int v) {
    to[++tot] = y, w[tot] = v, nxt[tot] = head[x], head[x] = tot;
    to[++tot] = x, w[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}

bool bfs() {
    memset(dep, 0, sizeof(dep));
    Q.push(s); dep[s] = 1;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i; i = nxt[i]) 
            if (w[i] && !dep[to[i]]) {
                dep[to[i]] = dep[u] + 1;
                Q.push(to[i]);
            }
    }
    return dep[t];
}

typec dfs(int x, typec flow) {
    if (x == t) return flow;
    typec rest = flow;
    for (int& i = cur[x]; i; i = nxt[i]) 
        if (w[i] && dep[to[i]] == dep[x] + 1) {
            typec k = dfs(to[i], min(w[i], rest));
            if (!k) dep[to[i]] = 0;
            rest -= k; w[i] -= k; w[i ^ 1] += k;
        }
    return flow - rest;
}

typec dinic() {
    typec ret = 0, flow;
    while (bfs()) {
        memcpy(cur, head, sizeof(cur));
        while (flow = dfs(s, oo)) ret += flow;
    } 
    return ret;
}

int main() {
    cin >> n >> m >> g;
    s = 0; t = n + m + 1;
    for (int i = 1;i <= n; ++i) cin >> A[i];
    for (int i = 1,x;i <= n; ++i) {
        cin >> x;
        if (A[i]) add(s, i, x);
        else add(i, t, x);
    }

    for (int i = 1,x,y,z;i <= m; ++i) {
        int op, k, neg;
        cin >> op >> W[i] >> k;
        sum += W[i];
        for (int j = 1;j <= k; ++j) {
            cin >> x; 
            if (op) add(n+i, x, oo);
            else add(x, n+i, oo);
        }
        cin >> neg;
        if (op) add(s, n+i, W[i] + neg*g);
        else add(n+i, t, W[i] + neg*g);
    }
    cout << sum - dinic() << endl;
    return 0;
}