最小割

习题

洛谷P2762洛谷P1361

\(n\) 个实验 \(m\) 个仪器, 做第 \(i\) 个实验需要若干个仪器, 奖金 \(p_i\).

购买第 \(i\) 个仪器需要 \(w_i\), 求最大净收益, 以及具体方案.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template <class T>
struct Flow {
    const int n;
    vector<pair<int, T>> edges;
    vector<vector<int>> adj;
    vector<int> cur, dep;
    Flow(int n) : n(n), adj(n) {}
    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &idx : adj[u]) {
                auto [to, w] = edges[idx];
                if (w > 0 && dep[to] == -1) {
                    dep[to] = dep[u] + 1;
                    if (to == t) {
                        return true;
                    }
                    q.push(to);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        T res = f;
        for (int &i = cur[u] ; i < (int) adj[u].size() ; i++) {
            int idx = adj[u][i];
            auto [to, w] = edges[idx];
            if (w > 0 and dep[to] == dep[u] + 1) {
                T out = dfs(to, t, min(res, w));
                edges[idx].second -= out;
                edges[idx ^ 1].second += out;
                res -= out;
                if (res == 0) {
                    return f;
                }
            }
        }
        return f - res;
    }
    void add(int u, int v, T c) {
        adj[u].push_back(edges.size());
        edges.push_back({v, c});
        adj[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    T dinic(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }
}; // Flow
int main() {
    int n, m;
    cin >> n >> m;
    Flow<i64> flow(n + m + 5);
    i64 ans = 0;
    int s = n + m + 1, t = n + m + 2;
    for (int i = 1 ; i <= n ; i++) {
        i64 value;
        cin >> value;
        ans += value;
        flow.add(s, i, value);
        string str;
        getline(cin, str);
        stringstream ss(str);
        while (ss >> value) {
            flow.add(i, n + value, numeric_limits<i64>::max());
        }
    }
    for (int i = 1 ; i <= m ; i++) {
        i64 cost;
        cin >> cost;
        flow.add(n + i, t, cost);
    }
    ans -= flow.dinic(s, t);
    for (int i = 1 ; i <= n ; i++) {
        if (flow.dep[i] > 0) {
            cout << i << " ";
        }
    }
    cout << "\n";
    for (int i = 1 ; i <= m ; i++) {
        if (flow.dep[n + i] > 0) {
            cout << i << " ";
        }
    }
    cout << "\n";
    cout << ans << "\n";
    return 0;
}

P1361 小M的作物 - 洛谷

\(n\) 个作物, 第 \(i\) 个作物种植在 \(A\) 可得收益 \(a_i\), 种植在 \(B\) 可得收益 \(b_i\)

有 \(m\) 种组合, 组合内的作物共同种在 \(A\) 可收益 \(c_1\), 共同种在 \(B\) 可收益 \(c_2\), 求最大收益.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template <class T>
struct Flow {
    const int n;
    vector<pair<int, T>> edges;
    vector<vector<int>> adj;
    vector<int> cur, dep;
    Flow(int n) : n(n), adj(n) {}
    bool bfs(int s, int t) {
        dep.assign(n, -1);
        queue<int> q;
        dep[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &idx : adj[u]) {
                auto [to, w] = edges[idx];
                if (w > 0 && dep[to] == -1) {
                    dep[to] = dep[u] + 1;
                    if (to == t) {
                        return true;
                    }
                    q.push(to);
                }
            }
        }
        return false;
    }
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        T res = f;
        for (int &i = cur[u] ; i < (int) adj[u].size() ; i++) {
            int idx = adj[u][i];
            auto [to, w] = edges[idx];
            if (w > 0 and dep[to] == dep[u] + 1) {
                T out = dfs(to, t, min(res, w));
                edges[idx].second -= out;
                edges[idx ^ 1].second += out;
                res -= out;
                if (res == 0) {
                    return f;
                }
            }
        }
        return f - res;
    }
    void add(int u, int v, T c) {
        adj[u].push_back(edges.size());
        edges.push_back({v, c});
        adj[v].push_back(edges.size());
        edges.push_back({u, 0});
    }

    T dinic(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, numeric_limits<T>::max());
        }
        return ans;
    }
}; // Flow
int a[1005], b[1005];
int main() {
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        ans += a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> b[i];
        ans += b[i];
    }
    int m;
    cin >> m;
    Flow<i64> flow(n + 2 * m + 4);
    int s = n + 1, t = n + 2;
    for (int i = 1 ; i <= n ; i++) {
        flow.add(s, i, a[i]);
        flow.add(i, t, b[i]);
    }
    int x1 = n + 3; // 在 A 的组合
    int x2 = n + 3 + m; // 在 B 的组合
    for (int i = 1 ; i <= m ; i++) {
        int k, c1, c2;
        cin >> k >> c1 >> c2;
        flow.add(s, x1 + i, c1);
        flow.add(x2 + i, t, c2);
        ans += c1 + c2;
        for (int j = 0 ; j < k ; j++) {
            int x;
            cin >> x;
            flow.add(x1 + i, x, numeric_limits<i64>::max());
            flow.add(x, x2 + i, numeric_limits<i64>::max());
        }
    }
    cout << ans - flow.dinic(s, t);
    return 0;
}