QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603629#602. 最小费用最大流(随机数据)shiqiaqiaya100 ✓778ms4256kbC++179.1kb2024-10-01 17:55:272024-10-01 17:55:27

Judging History

This is the latest submission verdict.

  • [2024-10-01 17:55:27]
  • Judged
  • Verdict: 100
  • Time: 778ms
  • Memory: 4256kb
  • [2024-10-01 17:55:27]
  • Submitted

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

template<class type = int>
struct Dinic : vector<vector<int>> {    // O(n^2 * m),二分图最大匹配 O(n^0.5 * m)
    struct Edge {
        int v;
        type c;
        Edge(int v, type c) : v(v), c(c) {}
    };

    vector<Edge> e;
    vector<int> cur, h;
    Dinic(int n) : vector(n) {}
    void add(int u, int v, type c) {
        at(u).emplace_back(e.size()), e.emplace_back(v, c);
        at(v).emplace_back(e.size()), e.emplace_back(u, 0);
    }

    int bfs(int & s, int & t) {
        h.assign(size(), numeric_limits<int>::max());
        queue<int> q;
        h[s] = 0, q.emplace(s);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (auto & i : at(u)) {
                auto & [v, c] = e[i];
                if (c > 0 && h[v] > h[u] + 1) h[v] = h[u] + 1, q.emplace(v);
            }
        }
        return h[t] != numeric_limits<int>::max();
    }
    type dfs(int u, int & t, type flow) {
        if (u == t) return flow;
        type ret = flow, a;
        for (int & i = cur[u]; i < at(u).size(); i++) {
            auto & [v, c] = e[at(u)[i]];
            if (c > 0 && h[v] == h[u] + 1 && (a = dfs(v, t, min(ret, c)))) {
                ret -= a, c -= a, e[at(u)[i] ^ 1].c += a;
                if (ret == 0) return flow;
            }
        }
        return flow - ret;
    }
    type maxflow(int s, int t, type flow = 0) {
        while (bfs(s, t)) {
            cur.assign(size(), 0), flow += dfs(s, t, numeric_limits<type>::max());
        }
        return flow;
    }
};

template<class type = int>
struct ISAP : vector<vector<int>> { // O(n^2 * m)
    struct Edge {
        int v;
        type c;
        Edge(int v, type c) : v(v), c(c) {}
    };

    vector<Edge> e;
    vector<int> cur, h, gap;
    ISAP(int n) : vector(n) {}
    void add(int u, int v, type c) {
        at(u).emplace_back(e.size()), e.emplace_back(v, c);
        at(v).emplace_back(e.size()), e.emplace_back(u, 0);
    }

    void bfs(int & t) {   // 反向bfs
        h.assign(size(), numeric_limits<int>::max()), gap.assign(size() + 2, 0);
        queue<int> q;
        h[t] = 0, gap[h[t]]++, q.emplace(t);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (auto & i : at(u)) {
                auto & [v, c] = e[i];
                if (e[i ^ 1].v && h[v] > h[u] + 1) h[v] = h[u] + 1, gap[h[v]]++, q.emplace(v);
            }
        }
    }
    type dfs(int u, int & s, int & t, type flow) {
        if (u == t) return flow;
        type ret = flow, a;
        for (int & i = cur[u]; i < at(u).size(); i++) {
            auto & [v, c] = e[at(u)[i]];
            if (c > 0 && h[v] + 1 == h[u] && (a = dfs(v, s, t, min(ret, c)))) {
                ret -= a, c -= a, e[at(u)[i] ^ 1].c += a;
                if (ret == 0) return flow;
            }
        }
        if (--gap[h[u]] == 0) h[s] = size();
        return gap[++h[u]]++, flow - ret;
    }
    type maxflow(int s, int t, type flow = 0) {
        for (bfs(t); h[s] < size(); ) {
            cur.assign(size(), 0), flow += dfs(s, s, t, numeric_limits<type>::max());
        }
        return flow;
    }
};

template<class type = int>
struct HLPP : vector<vector<int>> { // O(n^2 * sqrt(m))
    struct Edge {
        int v;
        type c;
        Edge(int v, type c) : v(v), c(c) {}
    };

    vector<Edge> e;
    vector<int> h, gap;
    int level = 0;
    vector<type> ex;
    vector<stack<int>> B;
    HLPP(int n) : vector(n) {}
    void add(int u, int v, type c) {
        at(u).emplace_back(e.size()), e.emplace_back(v, c);
        at(v).emplace_back(e.size()), e.emplace_back(u, 0);
    }

    int bfs(int & s, int & t) {   // 反向bfs
        h.assign(size(), numeric_limits<int>::max()), gap.assign(size() + 2, 0);
        queue<int> q;
        h[t] = 0, gap[h[t]]++, q.emplace(t);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (auto & i : at(u)) {
                auto & [v, c] = e[i];
                if (e[i ^ 1].v && h[v] > h[u] + 1) h[v] = h[u] + 1, gap[h[v]]++, q.emplace(v);
            }
        }
        return h[s] != numeric_limits<int>::max();
    }
    int push(int u, int & s, int & t) {
        int init = u == s;
        for (auto & i : at(u)) {
            auto & [v, c] = e[i];
            if (!init && h[u] != h[v] + 1 || !c || h[v] == numeric_limits<int>::max()) continue;
            type k = init ? c : min(c, ex[u]);
            if (v != s && v != t && !ex[v]) B[h[v]].push(v), level = max(level, h[v]);
            ex[u] -= k, ex[v] += k, c -= k, e[i ^ 1].c += k;
            if (!ex[u]) return 0;
        }
        return 1;
    }
    void relabel(int u) {
        h[u] = numeric_limits<int>::max();
        for (auto & i : at(u)) {
            if (e[i].c) h[u] = min(h[u], h[e[i].v]);
        }
        if (++h[u] < size()) B[h[u]].push(u), level = max(level, h[u]), ++gap[h[u]];
    }
    int slect() {
        for ( ; level > -1 && B[level].size() == 0; level--);
        return level == -1 ? 0 : B[level].top();
    }
    type maxflow(int s, int t, type flow = 0) {
        if (!bfs(s, t)) return 0;
        ex.assign(size(), 0), B.assign(size(), stack<int>());
        h[s] = size(), push(s, s, t);
        for (int u = 0; u = slect(); ) {
            B[level].pop();
            if (push(u, s, t)) {
                if (--gap[h[u]] == 0) for (int i = 0; i < size(); i++) {
                    if (i != s && h[i] > h[u] && h[i] < size() + 1) h[i] = size() + 1;
                }
                relabel(u);
            }
        }
        return ex[t];
    }
};

template <class type = int>
struct MCMF : vector<vector<int>> {
    struct Edge {
        int v;
        type c, f;  // 容量,费用
        Edge(int v, type c, type f) : v(v), c(c), f(f) {}
    };

    vector<Edge> e;
    vector<type> h, dis;
    vector<int> pre;
    MCMF(int n) : vector(n) {}
    void add(int u, int v, type c, type f) {
        at(u).emplace_back(e.size()), e.emplace_back(v, c, f);
        at(v).emplace_back(e.size()), e.emplace_back(u, 0, -f);
    }

    int dijkstra(int & s, int & t) {
        dis.assign(size(), numeric_limits<type>::max()), pre.assign(size(), -1);
        std::priority_queue<pair<type, int>, vector<pair<type, int>>, greater<>> q;
        dis[s] = 0, q.emplace(0, s);
        while (q.size()) {
            auto [d, u] = q.top(); q.pop();
            if (dis[u] < d) continue;
            for (auto & i : at(u)) {
                auto & [v, c, f] = e[i];
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f, pre[v] = i;
                    q.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != numeric_limits<type>::max();
    }
    void spfa(int & s, int & t) {   // 存在负权边
        h.assign(size(), numeric_limits<type>::max());
        vector<int> vis(size());
        queue<int> q;
        h[s] = 0, vis[s] = 1, q.push(s);
        while (q.size()) {
            int u = q.front(); q.pop(), vis[u] = 0;
            for (auto & i : at(u)) {
                auto & [v, c, f] = e[i];
                if (c > 0 && h[v] > h[u] + f) {
                    h[v] = h[u] + f;
                    if (!vis[v]) vis[v] = 1, q.push(v);
                }
            }
        }
    }
    array<type, 2> mncmxf(int s, int t, int flag, type flow = 0, type cost = 0) {
        if (flag) spfa(s, t);   // 若存在负权边,也可以使用消负权法
        else h.assign(size(), 0);   // 若全为正权值
        while (dijkstra(s, t)) {
            type a = numeric_limits<type>::max();
            for (int i = 0; i < size(); h[i++] += dis[i]);
            for (int i = t; i != s; a = min(a, e[pre[i]].c), i = e[pre[i] ^ 1].v);
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= a, e[pre[i] ^ 1].c += a;
            }
            flow += a, cost += a * h[t];
        }
        return {flow, cost};
    }
};

void QAQ() {
    int n, m;
    cin >> n >> m;

    MCMF adj(n + 1);

    for (int i = 0, u, v, c, f; i < m; i++) {
        cin >> u >> v >> c >> f;
        adj.add(u, v, c, f);
    }

    auto [flow, cost] = adj.mncmxf(1, n, 0);

    cout << flow << " " << cost << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3720kb

input:

8 27
2 3 2147483647 100
1 3 1 100
2 4 2147483647 10
1 4 1 10
2 4 2147483647 10
1 4 1 10
2 8 3 0
3 5 2147483647 100
1 5 1 100
3 8 1 0
3 2 2147483647 0
4 5 2147483647 10
1 5 1 10
4 8 1 0
4 2 2147483647 0
5 6 2147483647 1
1 6 1 1
5 6 2147483647 1
1 6 1 1
5 7 2147483647 1
1 7 1 1
5 8 3 0
5 2 2147483647 ...

output:

8 243

result:

ok 2 number(s): "8 243"

Test #2:

score: 10
Accepted
time: 0ms
memory: 3692kb

input:

12 49
2 10 2147483647 5
1 10 1 5
2 5 2147483647 50
1 5 1 50
2 9 2147483647 8
1 9 1 8
2 8 2147483647 47
1 8 1 47
2 11 2147483647 17
1 11 1 17
2 12 5 0
3 12 0 0
3 2 2147483647 0
4 6 2147483647 18
1 6 1 18
4 11 2147483647 12
1 11 1 12
4 9 2147483647 14
1 9 1 14
4 12 3 0
4 2 2147483647 0
5 11 2147483647...

output:

15 436

result:

ok 2 number(s): "15 436"

Test #3:

score: 10
Accepted
time: 1ms
memory: 3916kb

input:

27 169
2 15 2147483647 24
1 15 1 24
2 19 2147483647 96
1 19 1 96
2 12 2147483647 49
1 12 1 49
2 13 2147483647 75
1 13 1 75
2 24 2147483647 2
1 24 1 2
2 27 5 0
3 27 0 0
3 2 2147483647 0
4 11 2147483647 99
1 11 1 99
4 3 2147483647 85
1 3 1 85
4 27 2 0
4 2 2147483647 0
5 27 0 0
5 2 2147483647 0
6 9 214...

output:

60 4338

result:

ok 2 number(s): "60 4338"

Test #4:

score: 10
Accepted
time: 25ms
memory: 4008kb

input:

77 2149
2 42 2147483647 33
1 42 1 33
2 68 2147483647 30
1 68 1 30
2 76 2147483647 13
1 76 1 13
2 51 2147483647 93
1 51 1 93
2 12 2147483647 39
1 12 1 39
2 57 2147483647 74
1 57 1 74
2 70 2147483647 21
1 70 1 21
2 73 2147483647 24
1 73 1 24
2 52 2147483647 54
1 52 1 54
2 15 2147483647 99
1 15 1 99
2 ...

output:

1000 74606

result:

ok 2 number(s): "1000 74606"

Test #5:

score: 10
Accepted
time: 91ms
memory: 3884kb

input:

102 4199
2 48 2147483647 42
1 48 1 42
2 85 2147483647 50
1 85 1 50
2 22 2147483647 83
1 22 1 83
2 95 2147483647 97
1 95 1 97
2 82 2147483647 34
1 82 1 34
2 25 2147483647 72
1 25 1 72
2 4 2147483647 17
1 4 1 17
2 47 2147483647 10
1 47 1 10
2 71 2147483647 12
1 71 1 12
2 68 2147483647 39
1 68 1 39
2 2...

output:

2000 161420

result:

ok 2 number(s): "2000 161420"

Test #6:

score: 10
Accepted
time: 96ms
memory: 3876kb

input:

102 4199
2 79 2147483647 13
1 79 1 13
2 83 2147483647 73
1 83 1 73
2 75 2147483647 90
1 75 1 90
2 30 2147483647 92
1 30 1 92
2 54 2147483647 25
1 54 1 25
2 66 2147483647 53
1 66 1 53
2 52 2147483647 37
1 52 1 37
2 63 2147483647 46
1 63 1 46
2 11 2147483647 20
1 11 1 20
2 55 2147483647 53
1 55 1 53
2...

output:

2000 143072

result:

ok 2 number(s): "2000 143072"

Test #7:

score: 10
Accepted
time: 95ms
memory: 3848kb

input:

102 4199
2 39 2147483647 45
1 39 1 45
2 51 2147483647 11
1 51 1 11
2 86 2147483647 63
1 86 1 63
2 23 2147483647 46
1 23 1 46
2 48 2147483647 63
1 48 1 63
2 87 2147483647 8
1 87 1 8
2 73 2147483647 63
1 73 1 63
2 5 2147483647 52
1 5 1 52
2 80 2147483647 21
1 80 1 21
2 31 2147483647 44
1 31 1 44
2 101...

output:

2000 146132

result:

ok 2 number(s): "2000 146132"

Test #8:

score: 10
Accepted
time: 750ms
memory: 4256kb

input:

302 10599
2 72 2147483647 169
1 72 1 169
2 260 2147483647 165
1 260 1 165
2 12 2147483647 108
1 12 1 108
2 16 2147483647 26
1 16 1 26
2 28 2147483647 148
1 28 1 148
2 7 2147483647 74
1 7 1 74
2 139 2147483647 199
1 139 1 199
2 231 2147483647 9
1 231 1 9
2 287 2147483647 123
1 287 1 123
2 135 2147483...

output:

5000 1106316

result:

ok 2 number(s): "5000 1106316"

Test #9:

score: 10
Accepted
time: 778ms
memory: 4192kb

input:

302 10599
2 222 2147483647 132
1 222 1 132
2 17 2147483647 7
1 17 1 7
2 177 2147483647 253
1 177 1 253
2 90 2147483647 195
1 90 1 195
2 128 2147483647 289
1 128 1 289
2 42 2147483647 193
1 42 1 193
2 213 2147483647 133
1 213 1 133
2 263 2147483647 293
1 263 1 293
2 50 2147483647 155
1 50 1 155
2 228...

output:

5000 1290871

result:

ok 2 number(s): "5000 1290871"

Test #10:

score: 10
Accepted
time: 753ms
memory: 4252kb

input:

302 10599
2 176 2147483647 289
1 176 1 289
2 190 2147483647 99
1 190 1 99
2 10 2147483647 96
1 10 1 96
2 240 2147483647 165
1 240 1 165
2 273 2147483647 205
1 273 1 205
2 248 2147483647 194
1 248 1 194
2 220 2147483647 122
1 220 1 122
2 194 2147483647 167
1 194 1 167
2 8 2147483647 67
1 8 1 67
2 227...

output:

5000 1395897

result:

ok 2 number(s): "5000 1395897"