概要

\(N\) 個の島をすべて連結にするために必要な橋の建設コストの最小値を求める問題です。これは典型的な最小全域木 (Minimum Spanning Tree, MST) の問題です。

考察

重要な気づき

1. グラフ理論への言い換え: 島を頂点、橋を辺と考えると、「すべての島が行き来できる」とは「グラフが連結である」ことを意味します。

2. 必要な辺の数: \(N\) 個の頂点を連結にするには、最低でも \(N-1\) 本の辺が必要です。また、\(N-1\) 本で十分です（木構造になる）。

3. コスト最小化: \(N-1\) 本の辺を選ぶとき、コストの総和を最小にしたい → これが最小全域木問題です。

素朴なアプローチの問題点

すべての辺の組み合わせを試すと、\(M\) 本から \(N-1\) 本を選ぶ組み合わせは \(\binom{M}{N-1}\) 通りあり、指数的に増加するためTLEになります。

解決策

クラスカル法を使えば、辺をコスト順にソートして貪欲に選ぶだけで最小全域木が構築できます。

アルゴリズム

クラスカル法 (Kruskal’s Algorithm) を使用します。

手順

1. すべての辺をコストの昇順にソートする
2. Union-Find（素集合データ構造）を用意する
3. コストが小さい辺から順に見ていく：
   • その辺の両端が異なる連結成分に属するなら、辺を採用して連結成分を統合
   • 同じ連結成分に属するなら、辺を採用するとサイクルができるのでスキップ
4. \(N-1\) 本の辺が採用されたら終了
5. 最終的に \(N-1\) 本採用できなければ連結にできないので -1 を出力

具体例

\(N=4\)、辺が \((1,2,10), (2,3,5), (3,4,8), (1,4,20), (2,4,15)\) の場合：

1. ソート後: \((2,3,5), (3,4,8), (1,2,10), (2,4,15), (1,4,20)\)
2. \((2,3,5)\) を採用 → {2,3} が連結
3. \((3,4,8)\) を採用 → {2,3,4} が連結
4. \((1,2,10)\) を採用 → {1,2,3,4} が連結
5. 3本採用完了！総コスト = \(5 + 8 + 10 = 23\)

計算量

• 時間計算量: \(O(M \log M)\)

  • 辺のソート: \(O(M \log M)\)
  • Union-Find操作（経路圧縮＋ランク付き）: 各操作ほぼ \(O(1)\)、全体で \(O(M \cdot \alpha(N))\) ≈ \(O(M)\)

• 空間計算量: \(O(N + M)\)

  • Union-Find用の配列: \(O(N)\)
  • 辺のリスト: \(O(M)\)

実装のポイント

1. Union-Find の実装: 経路圧縮とランクによる統合を組み合わせることで、操作をほぼ定数時間で行える。

2. \(N = 1\) の特殊ケース: 島が1つだけなら橋は不要でコストは \(0\)。

3. 連結判定: 採用した辺の数が \(N-1\) 本になったかで判定できる。

4. オーバーフロー対策: コストは最大 \(10^9\)、辺は最大 \(N-1 \approx 10^5\) 本なので、総コストは最大約 \(10^{14}\)。Pythonでは整数のオーバーフローを気にする必要はない。

5. 入力の高速化: sys.stdin.read() で一括読み込みすることで、大量の入力を高速に処理できる。

   ソースコード

import sys
from typing import List, Tuple

def find(parent: List[int], x: int) -> int:
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent: List[int], rank: List[int], x: int, y: int) -> bool:
    px, py = find(parent, x), find(parent, y)
    if px == py:
        return False
    if rank[px] < rank[py]:
        px, py = py, px
    parent[py] = px
    if rank[px] == rank[py]:
        rank[px] += 1
    return True

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    if N == 1:
        print(0)
        return
    
    edges: List[Tuple[int, int, int]] = []
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        edges.append((c, u, v))
    
    # Sort edges by cost (Kruskal's algorithm)
    edges.sort()
    
    parent = list(range(N + 1))
    rank = [0] * (N + 1)
    
    total_cost = 0
    edge_count = 0
    
    for c, u, v in edges:
        if union(parent, rank, u, v):
            total_cost += c
            edge_count += 1
            if edge_count == N - 1:
                break
    
    if edge_count == N - 1:
        print(total_cost)
    else:
        print(-1)

if __name__ == "__main__":
    solve()

---

この解説は claude4.5opus によって生成されました。