跳转至

费用流

例题

P3381 【模板】最小费用最大流 - 洛谷

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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 MCF {
    struct Edge {
        int to;
        T cost, flow;
    };
    const int n;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<T> h, dist;
    vector<int> pre;
    MCF(int n) : n(n), adj(n) {}
    bool dijkstra(int s, int t) {
        dist.assign(n, numeric_limits<T>::max());
        pre.assign(n, -1);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;
        dist[s] = 0;
        q.push({0, s});
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (dist[u] < d) {
                continue;
            }
            for (auto &idx : adj[u]) {
                auto [to, cost, flow] = edges[idx];
                if (cost > 0 && dist[to] > d + h[u] - h[to] + flow) {
                    dist[to] = d + h[u] - h[to] + flow;
                    pre[to] = idx;
                    q.push({dist[to], to});
                }
            }
        }
        return dist[t] != numeric_limits<T>::max();
    }
    void add(int x, int y, int flow, int cost) {
        if (cost < 0) { // ** 删除 <=> 最大流
            adj[x].push_back(edges.size());
            edges.push_back({y, 0, cost});
            adj[y].push_back(edges.size());
            edges.push_back({x, flow, -cost});
        } else // **
            adj[x].push_back(edges.size()),
            edges.push_back({y, flow, cost}),
            adj[y].push_back(edges.size()),
            edges.push_back({x, 0, -cost});
    }
    pair<T, T> work(int s, int t) {
        int flow = 0;
        T cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0 ; i < n ; ++i) {
                h[i] += dist[i];
            }
            T aug = numeric_limits<T>::max();
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                aug = std::min(aug, edges[pre[i]].cost);
            }
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                edges[pre[i]].cost -= aug;
                edges[pre[i] ^ 1].cost += aug;
            }
            flow += aug;
            cost += T(aug) * h[t];
        }
        return {flow, cost};
    }
}; // MCF
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    MCF<i64> mcf(n + 1);
    for (int i = 0 ; i < m ; i++) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        mcf.add(u, v, w, c);
    }
    auto [flow, cost] = mcf.work(s, t);
    cout << flow << " " << cost << "\n";
    return 0;
}
习题

P3358 最长k可重区间集问题 - 洛谷

已知 \(k\) 和 \(n\) 个开区间, \((L_i,R_i)\), 每个点至多被 \(k\) 个区间覆盖

问任选开区间所能得到的区间长度的和的最大值.

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#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 MCF {
    struct Edge {
        int to;
        T cost, flow;
    };
    const int n;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<T> h, dist;
    vector<int> pre;
    MCF(int n) : n(n), adj(n) {}
    bool dijkstra(int s, int t) {
        dist.assign(n, numeric_limits<T>::max());
        pre.assign(n, -1);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;
        dist[s] = 0;
        q.push({0, s});
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (dist[u] < d) {
                continue;
            }
            for (auto &idx : adj[u]) {
                auto [to, cost, flow] = edges[idx];
                if (cost > 0 && dist[to] > d + h[u] - h[to] + flow) {
                    dist[to] = d + h[u] - h[to] + flow;
                    pre[to] = idx;
                    q.push({dist[to], to});
                }
            }
        }
        return dist[t] != numeric_limits<T>::max();
    }
    void add(int x, int y, int flow, int cost) {
        adj[x].push_back(edges.size()),
        edges.push_back({y, flow, cost}),
        adj[y].push_back(edges.size()),
        edges.push_back({x, 0, -cost});
    }
    pair<T, T> work(int s, int t) {
        int flow = 0;
        T cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0 ; i < n ; ++i) {
                h[i] += dist[i];
            }
            T aug = numeric_limits<T>::max();
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                aug = std::min(aug, edges[pre[i]].cost);
            }
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                edges[pre[i]].cost -= aug;
                edges[pre[i] ^ 1].cost += aug;
            }
            flow += aug;
            cost += T(aug) * h[t];
        }
        return {flow, cost};
    }
}; // MCF
int main() {
    int n, k;
    cin >> n >> k;
    vector<array<int, 2>> a(n + 1);
    vector<int> idx(1, 0);
    for (int i = 1 ; i <= n ; i++) {
        int L, R;
        cin >> L >> R;
        a[i] = {L, R};
        idx.push_back(L);
        idx.push_back(R);
    }

    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    int len = idx.size() - 1;
    int s = len + 1, t = s + 1;
    MCF<int> mcf(t + 1);
    mcf.add(s, 1, k, 0);
    for (int i = 1 ; i < len ; i++) {
        mcf.add(i, i + 1, 999999LL, 0);
    }
    mcf.add(len, t, 999999LL, 0);
    for (int i = 1 ; i <= n ; i++) {
        int L = a[i][1] - a[i][0];
        int x = lower_bound(begin(idx), end(idx), a[i][0]) - begin(idx);
        int y = lower_bound(begin(idx), end(idx), a[i][1]) - begin(idx);
        mcf.add(x, y, 1, -L);
    }
    auto [flow, cost] = mcf.work(s, t);
    cout << -cost;
    return 0;
}

P2770 航空路线问题 - 洛谷

\(n\) 个点, \(m\) 条无向边, 问从 \(1\) 到 \(n\) 再回到 \(1\) 且不能经过除了 \(1\) 之外的点两次的最长路径.

对每个点分为出点和入点,

对于每个点, 自己的入点连接自己的出点, 容量为 \(1\), 费用为 \(1\), 起点和终点的容量为 \(2\),

对于每条边出点连接入点, 容量为 \(1\), 费用为 \(0\), 跑最大费用最大流.

最大流为 \(2\), 说明从 \(1\) 到 \(n\) 有两条不相交的路径,

最大流为 \(1\) 时, 要特判是否有直接从 \(1\) 到 \(n\) 的边,

其余情况均为无解.

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#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 MCF {
    struct Edge {
        int to;
        T cost, flow;
    };
    const int n;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<T> h, dist;
    vector<int> pre;
    MCF(int n) : n(n), adj(n) {}
    bool dijkstra(int s, int t) {
        dist.assign(n, numeric_limits<T>::max());
        pre.assign(n, -1);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> q;
        dist[s] = 0;
        q.push({0, s});
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (dist[u] < d) {
                continue;
            }
            for (auto &idx : adj[u]) {
                auto [to, cost, flow] = edges[idx];
                if (cost > 0 && dist[to] > d + h[u] - h[to] + flow) {
                    dist[to] = d + h[u] - h[to] + flow;
                    pre[to] = idx;
                    q.push({dist[to], to});
                }
            }
        }
        return dist[t] != numeric_limits<T>::max();
    }
    void add(int x, int y, int flow, int cost) {
        adj[x].push_back(edges.size()),
        edges.push_back({y, flow, cost}),
        adj[y].push_back(edges.size()),
        edges.push_back({x, 0, -cost});
    }
    pair<T, T> work(int s, int t) {
        int flow = 0;
        T cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0 ; i < n ; ++i) {
                h[i] += dist[i];
            }
            T aug = numeric_limits<T>::max();
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                aug = std::min(aug, edges[pre[i]].cost);
            }
            for (int i = t ; i != s ; i = edges[pre[i] ^ 1].to) {
                edges[pre[i]].cost -= aug;
                edges[pre[i] ^ 1].cost += aug;
            }
            flow += aug;
            cost += T(aug) * h[t];
        }
        return {flow, cost};
    }
}; // MCF
string a[105];
map<string, int> rev;
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        rev[a[i]] = i;
    }
    int s = 1, t = n + n;
    MCF<int> mcf(t + 1);
    for (int i = 1 ; i <= n ; i++) {
        mcf.add(i, n + i, 1 + (i == 1 || i == n), -1);
    }
    bool flag = false;
    for (int i = 1 ; i <= m ; i++) {
        string su, sv;
        cin >> su >> sv;
        int u = rev[su], v = rev[sv];
        if (u > v) swap(u, v);
        if (u == 1 && v == n) {
            flag = true;
        }
        mcf.add(n + u, v, 1, 0);
    }
    auto [flow, cost] = mcf.work(s, t);
    cost = -cost;
    if (flow == 1 && flag) {
        cout << 2 << "\n";
        cout << a[1] << "\n" << a[n] << "\n" << a[1] << "\n";
    } else if (flow == 2) {
        cout << cost - 2 << "\n";
        vector<bool> vis(2 * n + 1);
        function<void(int)> dfs = [&](int u) {
            vis[u] = true;
            cout << a[u - n] << "\n";
            for (auto &idx : mcf.adj[u]) {
                auto [to, flow, cost] = mcf.edges[idx];
                if (to == u - n) continue;
                if (flow != 0) continue;
                if (to > n) continue;
                dfs(to + n);
                break;
            }
        };
        dfs(1 + n);
        dfs = [&](int u) {
            for (auto &idx : mcf.adj[u]) {
                auto [to, flow, cost] = mcf.edges[idx];
                if (to == u - n) continue;
                if (vis[to + n]) continue;
                if (flow != 0) continue;
                if (to > n) continue;
                dfs(to + n);
                break;
            }
            cout << a[u - n] << "\n";
        };
        dfs(1 + n);
    } else {
        cout << "No Solution!\n";
    }
    return 0;
}