概要

与えられた橋の候補からいくつかを選び、全ての島が行き来できる（グラフが連結になる）ようにするための最小総コストを求める問題です。連結にできない場合は -1 を出力します。

考察

島を頂点、橋案を辺（コスト付き）とみなすと、「全頂点を連結にする最小コスト」は 最小全域木（MST: Minimum Spanning Tree） を求める問題そのものです。

• 連結なグラフを最小コストで作るには、無駄な辺（閉路を作る辺）は不要です。
  連結な \(N\) 頂点のグラフで閉路がないもの（木）は必ず辺数が \(N-1\) 本で、これより少ないと連結にできません。
• よって「コストが最小の連結な \(N-1\) 本の辺」を探せばよいです。

素朴に「辺の選び方を全探索」すると、辺は最大 \(2\times 10^5\) 本もあるため組合せ爆発で不可能です。また「安い順に辺を取る」だけだと、閉路を作る辺まで取ってしまい、最小にならない／必要本数が管理できない、という問題が起きます。

ここで重要なのが次の観察です：

• 安い辺から見ていき、閉路を作らないなら採用する
  という方針（Kruskal法）で MST を正しく構築できます。
• 「閉路を作るか？」の判定には、現在同じ連結成分にいるかどうかを高速に判定できる Union-Find（DSU） が有効です。

連結にできたかどうかは、採用した辺の本数が \(N-1\) 本に達したかで判定できます（達しなければ連結不可）。

アルゴリズム

Kruskal法 + Union-Find で最小全域木を作ります。

1. 全ての橋案（辺）をコスト \(C_i\) の昇順にソートする。
2. Union-Find を初期化（各島は別の連結成分）。
3. ソートした順に辺 \((u,v,c)\) を見ていく。
   • \(u\) と \(v\) が 別の連結成分なら採用し、コストに \(c\) を足し、Union-Find で成分を結合する。
   • 同じ成分なら採用すると閉路ができるのでスキップする。
4. 採用した辺数が \(N-1\) 本になったら終了。
5. 最後に
   • \(N=1\) なら最初から連結なので答えは \(0\)。
   • 採用辺数が \(N-1\) 本なら合計コストを出力。
   • そうでなければ -1（候補だけでは連結にできない）。

（簡単な例）
島が 4 つで、安い順に辺を見ていき、閉路にならないものだけ選ぶと、最終的に 3 本（\(N-1\) 本）で全島がつながった時点の合計が最小になります。

計算量

• 時間計算量: \(O(M\log M)\)（辺のソートが支配的。Union-Find 操作はほぼ \(O(1)\)）
• 空間計算量: \(O(N+M)\)（Union-Find と辺リスト）

実装のポイント

• 入力の島番号は \(1\) 始まりなので、実装では \(0\) 始まりに直す（u-1, v-1）。

• Union-Find は

  • 経路圧縮（find の高速化）
  • union by size（小さい木を大きい木にぶら下げる） を入れると高速で安定します。

• 辺を \(N-1\) 本採用したらそれ以上見る必要はないので、早期 break すると無駄が減ります。

• \(N=1\) のときは辺が不要なので必ず答えは \(0\)（この特例を入れておくと安全です）。

  ソースコード

import sys

class DSU:
    __slots__ = ("parent", "size")
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

def main():
    input = sys.stdin.buffer.readline
    N, M = 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()

    dsu = DSU(N)
    total = 0
    cnt = 0
    for c, u, v in edges:
        if dsu.union(u, v):
            total += c
            cnt += 1
            if cnt == N - 1:
                break

    if N == 1:
        print(0)
    elif cnt == N - 1:
        print(total)
    else:
        print(-1)

if __name__ == "__main__":
    main()

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