QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382375#602. 最小费用最大流(随机数据)Isrothy100 ✓145ms4388kbC++233.7kb2024-04-08 13:15:332024-04-08 13:15:33

Judging History

你现在查看的是最新测评结果

  • [2024-04-08 13:15:33]
  • 评测
  • 测评结果:100
  • 用时:145ms
  • 内存:4388kb
  • [2024-04-08 13:15:33]
  • 提交

answer

#include <cstdint>
#include <cstdio>
#include <queue>
#include <vector>
struct PrimalDual {
    static constexpr int64_t INF = 0x3f3f3f3f3f3f3f3f;
    struct Edge {
        int from, to;
        int64_t cap, cost, flow;
        Edge(int from, int to, int64_t cap, int64_t cost)
            : from(from), to(to), cap(cap), cost(cost), flow(0) {}
    };
    std::vector<Edge> edges;
    std::vector<std::vector<int>> adj;
    std::vector<int64_t> dis, h;
    std::vector<bool> vis, in_queue;
    int n;
    explicit PrimalDual(int n) : adj(n), dis(n), h(n), vis(n), in_queue(n), n(n) {}
    void add_edge(int u, int v, int64_t cap, int64_t cost) {
        adj[u].push_back((int) edges.size());
        edges.emplace_back(u, v, cap, cost);
        adj[v].push_back((int) edges.size());
        edges.emplace_back(v, u, 0, -cost);
    }
    void spfa(int t) {
        std::queue<int> q;
        std::vector<bool> in_queue(n, false);
        std::fill(dis.begin(), dis.end(), INF);
        dis[t] = 0;
        in_queue[t] = true;
        q.push(t);
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            in_queue[u] = false;
            for (auto i: adj[u]) {
                const auto &e = edges[i ^ 1];
                if (e.flow != e.cap && dis[u] + e.cost < dis[e.from]) {
                    dis[e.from] = dis[u] + e.cost;
                    if (!in_queue[e.from]) {
                        in_queue[e.from] = true;
                        q.push(e.from);
                    }
                }
            }
        }
    }
    void dijkstra(int t) {
        std::priority_queue<std::pair<int, int>> q;
        std::fill(dis.begin(), dis.end(), INF);
        dis[t] = 0;
        q.emplace(0, t);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] != -d) {
                continue;
            }
            for (auto i: adj[u]) {
                const auto &e = edges[i ^ 1];
                auto c = dis[u] + e.cost + h[u] - h[e.from];
                if (e.flow < e.cap && c < dis[e.from]) {
                    dis[e.from] = c;
                    q.emplace(-c, e.from);
                }
            }
        }
    }
    auto dfs(int u, int t, int64_t a) {
        if (u == t) {
            return a;
        }
        vis[u] = true;
        auto m = a;
        for (auto i: adj[u]) {
            auto &e = edges[i];
            if (e.flow < e.cap && !vis[e.to] && h[e.to] == h[u] - e.cost) {
                auto f = dfs(e.to, t, std::min(m, e.cap - e.flow));
                e.flow += f;
                edges[i ^ 1].flow -= f;
                m -= f;
                if (m == 0) {
                    break;
                }
            }
        }
        return a - m;
    }
    auto minimum_cost_flow(int s, int t) {
        int64_t flow = 0, cost = 0;
        for (spfa(t); dis[s] != INF; dijkstra(t)) {
            for (int i = 0; i < n; ++i) {
                h[i] += dis[i];
            }
            while (true) {
                std::fill(vis.begin(), vis.end(), false);
                if (auto f = dfs(s, t, INF)) {
                    flow += f;
                    cost += f * h[s];
                } else {
                    break;
                }
            }
        }
        return std::make_pair(flow, cost);
    }
};

int main() {
    int n, m;
    scanf("%u %u", &n, &m);
    PrimalDual pd(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        int64_t c, d;
        scanf("%u %u %llu %llu", &u, &v, &c, &d);
        pd.add_edge(u, v, c, d);
    }
    auto ans = pd.minimum_cost_flow(1, n);
    printf("%lld %lld\n", ans.first, ans.second);
    return 0;
}

詳細信息

Test #1:

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

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: 3720kb

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: 3804kb

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: 7ms
memory: 3924kb

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: 21ms
memory: 3904kb

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: 19ms
memory: 3924kb

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: 14ms
memory: 3928kb

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: 120ms
memory: 4332kb

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: 145ms
memory: 4228kb

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: 137ms
memory: 4388kb

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"