概要

すべての拠点を連結するケーブル集合のうち、

\[ \sum c_i + K \times \max c_i \]

を最小化する問題です。結論として、通常の最小全域木（MST）を作れば答えが求まります。

考察

まず、最終的に選ぶケーブル集合 \(S\) は、すべての拠点を連結していればよいです。

もし \(S\) に閉路が含まれている場合、その閉路上の辺を 1 本取り除いても連結性は保たれます。さらに、辺を取り除くことで

• 総コスト \(\sum c_i\) は減る
• 最大コスト \(\max c_i\) は増えない

ため、負荷指数は悪化しません。

したがって、最適解は必ず \(N-1\) 本の辺からなる全域木として考えれば十分です。

---

ここで問題は、

\[ \text{総コスト} + K \times \text{最大辺コスト} \]

を最小にする全域木を探すことになります。

一見すると、「総コスト」と「最大辺コスト」の両方を考える必要があるため、通常の最小全域木では不十分に見えるかもしれません。

しかし、最小全域木には次の重要な性質があります。

最小全域木は最大辺コストも最小にする

最小全域木は、総コストが最小であるだけでなく、全域木の中で使われる最大辺コストも最小になります。

これを「最小ボトルネック全域木」の性質と呼びます。

例えば、Kruskal 法で最小全域木を作ったとします。最後に選ばれた辺のコストを \(W\) とすると、この \(W\) がその最小全域木に含まれる最大辺コストです。

もしコストが \(W\) 未満の辺だけで全頂点を連結できるなら、Kruskal 法はコスト \(W\) の辺を使う前に全域木を完成できるはずです。しかし実際にはそうなっていないので、どんな全域木でもコスト \(W\) 以上の辺を少なくとも 1 本使う必要があります。

つまり、最小全域木の最大辺コストは、全域木全体の中で最小です。

---

最小全域木を \(T\)、任意の全域木を \(T'\) とすると、

\[ \sum_{e \in T} c_e \leq \sum_{e \in T'} c_e \]

かつ

\[ \max_{e \in T} c_e \leq \max_{e \in T'} c_e \]

が成り立ちます。

また、\(K \geq 0\) なので、

\[ \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \leq \sum_{e \in T'} c_e + K \times \max_{e \in T'} c_e \]

となります。

したがって、通常の最小全域木を求めれば、その負荷指数が最小値になります。

---

素朴にすべての辺の選び方を試すと \(2^M\) 通りあり、制約 \(M \leq 2 \times 10^5\) では到底間に合いません。

そこで、Kruskal 法を用いて効率よく最小全域木を構築します。

アルゴリズム

Kruskal 法を使います。

1. すべての辺をコストの昇順にソートする
2. Union-Find を用意する
3. コストが小さい辺から順に見る
4. その辺で異なる連結成分をつなげるなら採用する
5. 採用した辺のコストを総和に加える
6. 採用した辺のコストを最大コストとして更新する
   • 辺は昇順に見ているので、最後に採用した辺のコストが最大になる
7. \(N-1\) 本採用したら終了
8. 答えとして

\[ \text{総コスト} + K \times \text{最大コスト} \]

を出力する

計算量

• 時間計算量: \(O(M \log M)\)
  • 辺のソートに \(O(M \log M)\)
  • Union-Find の操作はほぼ \(O(M)\)
• 空間計算量: \(O(N + M)\)
  • 辺の情報に \(O(M)\)
  • Union-Find に \(O(N)\)

実装のポイント

Union-Find を使って、現在その辺を追加すると閉路ができるかを判定します。

ru = find(u)
rv = find(v)
if ru != rv:
    # 異なる連結成分なので採用

辺はコスト昇順に処理しているため、採用した辺の最大コストは毎回

max_c = c

として更新すれば十分です。

また、全域木にはちょうど \(N-1\) 本の辺が含まれるので、採用本数が \(N-1\) になった時点で処理を打ち切れます。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, c = map(int, input().split())
        edges.append((c, u - 1, v - 1))

    edges.sort()

    parent = list(range(N))
    size = [1] * N

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    max_c = 0
    cnt = 0

    for c, u, v in edges:
        ru = find(u)
        rv = find(v)
        if ru != rv:
            if size[ru] < size[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            size[ru] += size[rv]
            total += c
            max_c = c
            cnt += 1
            if cnt == N - 1:
                break

    print(total + K * max_c)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。