公式

D - 通信ネットワークの構築 / Construction of a Communication Network 解説 by MMNMM

負荷指数を最小にするような \(S\) は、（全拠点を連結にした上で）\(\displaystyle\sum _ {i\in S}c _ i\) を最小にするような \(S\) です。

証明

そのような \(S\) はクラスカル法によって得られます。

クラスカル法を実行する様子を考えると、候補 \(\displaystyle\argmax _ {i\in S}c _ i\) は最後に追加される辺で、それ以前に追加された辺からなる \(2\) つの連結成分 \(U,V\) を繋ぐものです。

クラスカル法のアルゴリズムから、\(U\) と \(V\) を繋ぐ辺はすべて \(\displaystyle\max _ {i\in S}c _ i\) 以上のコストを持ちます。

よって、すべての拠点間で通信可能なネットワークは \(\displaystyle\max _ {i\in S}c _ i\) 以上のコストのケーブルを含まなければなりません。

よって、\(\displaystyle\sum _ {i\in S}c _ i\) を最小にする \(S\) は同時に \(\displaystyle\max _ {i\in S}c _ i\) を最小にする \(S\) であることが示されたので、これが最小の負荷指数を与えることがわかりました。

よって、最小全域木を求める十分高速なアルゴリズムを使って \(S\) を求め、負荷指数を計算することでこの問題を解くことができました。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/dsu>
using namespace std;

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<tuple<int, int, int>> edges(M);
    for (auto& [u, v, c] : edges) {
        cin >> u >> v >> c;
        --u; // 0-indexed にしておく
        --v;
    }
    // 辺をコストの昇順にソート
    ranges::sort(edges, {}, [](auto p){return get<2>(p);});

    // 最小全域木を作り、コストの総和と最大値を求める
    atcoder::dsu uf(N);
    long sum_cost = 0, max_cost = 0;
    for (auto [u, v, c] : edges) {
        if (!uf.same(u, v)) {
            uf.merge(u, v);
            sum_cost += c;
            max_cost = max<long>(c, max_cost);
        }
    }
    cout << sum_cost + K * max_cost << endl;
    return 0;
}

from atcoder.dsu import DSU


N, M, K = map(int, input().split())

edges = []
for i in range(M):
    u, v, c = map(int, input().split())
    edges.append((u - 1, v - 1, c)) # 0-indexed にしておく
# 辺をコストの昇順にソート
edges.sort(key=lambda e: e[2])

# 最小全域木を作り、コストの総和と最大値を求める
uf = DSU(N)
sum_cost = 0
max_cost = 0
for u, v, c in edges:
    if not uf.same(u, v):
        uf.merge(u, v)
        sum_cost += c
        max_cost = max(c, max_cost)

print(sum_cost + K * max_cost)

投稿日時:
最終更新: