概要

特定の必須ケーブル（辺）を必ず含めるという条件のもとで、通信コストが最小となるネットワーク（最小全域木）を構築する問題です。

考察

全サーバーを連結にしつつ閉路を持たないネットワークを構築する問題は、グラフ理論において「最小全域木（Minimum Spanning Tree, MST）」を求める問題として知られています。最小全域木を求める代表的な手法にクラスカル法（Kruskal’s algorithm）があります。

通常のクラスカル法では、すべての辺をコストの小さい順（昇順）にソートし、「閉路ができないように辺を \(1\) 本ずつ追加していく」という貪欲法を行います。

しかし今回は「必ず含めなければならない \(K\) 本のケーブル」が指定されています。これをどう扱うかがポイントです。 直感的に考えると、「必須の \(K\) 本のケーブルを最初にすべて繋いでしまい、足りない部分をコストの低いケーブルで補う」というアプローチが思い浮かびます。実際、この方法で正しく最小コストを求めることができます。

注意点として、以下のケースでは全域木を作ることができないため -1 を出力する必要があります。 1. 必須の \(K\) 本のケーブルだけで閉路ができてしまう場合 全域木は閉路を持たないという条件に反するため、構築不可能です。 2. 利用可能なケーブルをすべて使っても、全サーバーを繋ぐことができない場合 最終的に選んだケーブルの本数が \(N-1\) 本に満たない場合、サーバー全体が連結になっていません。

アルゴリズム

閉路の判定や頂点の連結判定には、Union-Find（素集合データ構造）を使用します。

1. \(N\) 頂点の Union-Find を初期化します。
2. まず、必須の \(K\) 本のケーブルを順番に確認し、Union-Find を使ってサーバー同士を繋ぎます（unite 操作）。
   • このとき、繋ごうとした2つのサーバーがすでに同じグループに属している（＝閉路ができる）場合は、その時点で構築不可能と判断し -1 を出力して終了します。
   • 閉路ができなければ、そのケーブルのコストを合計に足し、使ったケーブルの本数を \(+1\) します。
3. 次に、必須ではない残りのケーブルを、敷設コスト \(W_i\) の小さい順（昇順）にソートします。
4. ソートしたケーブルを順番に見ていき、Union-Find で閉路ができないか確認しながら追加していきます。
   • 閉路ができない（繋ぐサーバーが異なるグループに属している）場合のみ、ケーブルを採用してコストを合計に足し、使った本数を \(+1\) します。
   • 使ったケーブルの本数が \(N-1\) 本に達したら、全域木が完成したことになるので探索を打ち切ります。
5. 最後に、使ったケーブルの本数がちょうど \(N-1\) 本であれば合計コストを出力し、足りなければ（全体が連結にならなかったので） -1 を出力します。

計算量

• 時間計算量: \(O(M \log M)\)
  • 必須ではない辺のソートに \(O(M \log M)\) の時間がかかります。
  • Union-Find の各操作は非常に高速（アッカーマン関数の逆関数 \(\alpha(N)\)）であり、辺の追加処理全体で \(O(M \alpha(N))\) となります。
  • したがって、全体の時間計算量はソート部分が支配的となり \(O(M \log M)\) です。
• 空間計算量: \(O(N + M)\)
  • Union-Find の配列に \(O(N)\)、辺の情報を保持するリストや集合（Set）に \(O(M)\) のメモリを使用します。

実装のポイント

• 1-indexed と 0-indexed の変換: 入力されるサーバーの番号やケーブルの番号は \(1\) から始まりますが、プログラム内部の配列や Union-Find では \(0\) から始まるインデックスとして扱うと実装がシンプルになります。

• 必須ケーブルの高速な判定: あるケーブルが必須かどうかを判定するために、必須ケーブルの番号を set（ハッシュテーブル）に入れておくと、\(O(1)\) で高速に判定できます。

• 再帰上限の引き上げ（Python特有）: Union-Find の find 関数で再帰呼び出しを使用するため、Python では sys.setrecursionlimit を用いて再帰の深さの上限を増やしておく必要があります（制約の \(N = 2 \times 10^5\) に対応するため）。

• 高速な入出力: 入力量が多いため、sys.stdin.read().split() を用いて入力を一括で読み込むと実行時間を大幅に短縮できます。

  ソースコード

import sys

sys.setrecursionlimit(300000)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    U = [0] * M
    V = [0] * M
    W = [0] * M
    
    idx = 3
    for i in range(M):
        U[i] = int(input_data[idx]) - 1
        V[i] = int(input_data[idx+1]) - 1
        W[i] = int(input_data[idx+2])
        idx += 3
        
    E = set()
    if K > 0:
        for _ in range(K):
            E.add(int(input_data[idx]) - 1)
            idx += 1
            
    uf = UnionFind(N)
    total_cost = 0
    edge_count = 0
    
    for i in E:
        u, v, w = U[i], V[i], W[i]
        if not uf.unite(u, v):
            print(-1)
            return
        total_cost += w
        edge_count += 1
        
    other_edges = []
    for i in range(M):
        if i not in E:
            other_edges.append((W[i], U[i], V[i]))
            
    other_edges.sort()
    
    for w, u, v in other_edges:
        if edge_count == N - 1:
            break
        if uf.unite(u, v):
            total_cost += w
            edge_count += 1
            
    if edge_count == N - 1:
        print(total_cost)
    else:
        print(-1)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。