#1196874 (C++23(gcc16)) No.1316 Maximum Minimum Spanning Tree

• 問題: No.1316 Maximum Minimum Spanning Tree
• ユーザー: Drtever
• 提出日時: 2026-11-04 18:01:35
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 8 ms / 2,000 ms
• コード長: 3,609 bytes
• コンパイル時間: 6,363 ms
• コンパイル使用メモリ: 371,464 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-11-04 18:02:12
• 合計ジャッジ時間: 10,048 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge7_0

ファイルパターン	結果
sample	AC * 4
other	AC * 78

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Dinic {
    struct Edge {
        int to, rev;
        ll cap;
    };

    int n;
    vector<vector<Edge>> g;
    vector<int> dep, cur;

    Dinic(int n) : n(n), g(n), dep(n), cur(n) {}

    void add(int u, int v, ll w) {
        Edge a = {v, (int)g[v].size(), w};
        Edge b = {u, (int)g[u].size(), 0};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    bool bfs(int s, int t) {
        fill(dep.begin(), dep.end(), -1);
        queue<int> q;
        q.push(s);
        dep[s] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (auto &e : g[u]) {
                if (e.cap > 0 && dep[e.to] == -1) {
                    dep[e.to] = dep[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return dep[t] != -1;
    }

    ll dfs(int u, int t, ll f) {
        if (u == t) return f;

        for (int &i = cur[u]; i < (int)g[u].size(); i++) {
            auto &e = g[u][i];

            if (e.cap <= 0 || dep[e.to] != dep[u] + 1)
                continue;

            ll x = dfs(e.to, t, min(f, e.cap));

            if (x) {
                e.cap -= x;
                g[e.to][e.rev].cap += x;
                return x;
            }
        }
        return 0;
    }

    ll flow(int s, int t) {
        ll res = 0;
        const ll INF = (1LL << 60);

        while (bfs(s, t)) {
            fill(cur.begin(), cur.end(), 0);

            while (ll f = dfs(s, t, INF)) {
                res += f;
            }
        }
        return res;
    }
};

struct Edge {
    int u, v;
    ll c, d;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    ll K;
    cin >> N >> M >> K;

    vector<Edge> e(M);

    for (auto &x : e) {
        cin >> x.u >> x.v >> x.c >> x.d;
        --x.u;
        --x.v;
    }

    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);

    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return e[a].c < e[b].c;
    });

    vector<ll> cnt(M, 0);

    ll total = 0;
    ll need = K * (N - 1);
    ll ans = 0;

    const ll INF = (1LL << 60);

    for (int id : ord) {
        if (total == need) break;

        // 计算每个顶点的度数（带重数）
        vector<ll> deg(N, 0);

        for (int i = 0; i < M; i++) {
            deg[e[i].u] += cnt[i];
            deg[e[i].v] += cnt[i];
        }

        int s = N;
        int t = N + 1;

        Dinic dinic(N + 2);

        // 顶点相关的边
        for (int v = 0; v < N; v++) {
            dinic.add(s, v, deg[v]);
            dinic.add(v, t, 2 * K);
        }

        // 已选择的边
        for (int i = 0; i < M; i++) {
            if (cnt[i] == 0) continue;

            int u = e[i].u;
            int v = e[i].v;

            // 无向边，容量为 cnt[i]
            dinic.add(u, v, cnt[i]);
            dinic.add(v, u, cnt[i]);
        }

        // 强制当前边的两个端点属于源点一侧
        dinic.add(s, e[id].u, INF);
        dinic.add(s, e[id].v, INF);

        // 最小割
        ll cut = dinic.flow(s, t);

        // 当前边最多还能添加的数量
        ll add = cut / 2 - total - K;

        // 受到 d[i] 和总需求的限制
        ll take = min({
            e[id].d,
            add,
            need - total
        });

        cnt[id] = take;
        total += take;
        ans += take * e[id].c;
    }

    if (total < need) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}