概要

すべての拠点を連結にする通信ケーブルの集合（全域木）のうち、「総コスト + \(K \times\) 最大コスト」として定義される「負荷指数」を最小化する問題です。

一見複雑な式に見えますが、グラフ理論における最小全域木（MST）の性質を利用することで、通常の最小全域木を求めるだけで最適解が得られます。

---

考察

1. 最適なネットワークは「木」になる

まず、選ぶケーブルの集合 \(S\) に閉路（ループ）が含まれている場合を考えます。閉路から最もコストの高いケーブルを1本取り除いても、すべての拠点は連結なままであり、かつ「総コスト」も「最大コスト」も減少（または不変）します。 したがって、負荷指数を最小化する最適なケーブルの集合 \(S\) は、余分な閉路を持たない全域木（Spanning Tree）になります。

2. 負荷指数の式を分析する

全域木 \(T\) に対する負荷指数は以下の式で表されます。 $\( \text{負荷指数}(T) = \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \)\( ここで、係数 \)K\( は非負整数（\)K \ge 0\(）です。 もし、**「総コスト \)\sum c_e\(」と「最大コスト \)\max c_e$」を同時に最小化できる全域木**が存在すれば、それが負荷指数を最小化する木になります。

3. 最小全域木（MST）の強力な性質

実は、クラスカル法などで求められる最小全域木（MST）には、以下の2つの性質が同時に成り立つことが知られています。

1. 総コストの最小性: すべての全域木の中で、辺の総和 \(\sum c_e\) が最小である。
2. ボトルネック全域木の性質: すべての全域木の中で、使われている辺の最大コスト \(\max c_e\) が最小である。

\(K \ge 0\) であるため、総コストと最大コストのどちらも最小化されている最小全域木は、それらの線形結合である「負荷指数」も確実に最小化します。

したがって、この問題は「与えられたグラフの最小全域木を求め、その総コストと最大辺コストから負荷指数を計算する」というシンプルな問題に帰着されます。

---

アルゴリズム

最小全域木を効率よく求めるために、クラスカル法（Kruskal’s algorithm）を使用します。

1. 辺のソート: すべてのケーブル（辺）をコストの昇順（小さい順）にソートします。
2. Union-Findの初期化: 拠点の連結状態を管理するために、サイズ \(N\) の Union-Find 木を用意します。
3. 辺の貪欲な追加:
   • コストの小さい辺から順に見ていきます。
   • その辺が結ぶ2つの拠点 \(u_i, v_i\) がまだ同じグループに属していない（連結でない）場合、その辺をネットワークに採用し、Union-Find で2つのグループを結合（union）します。
   • 採用した辺のコストを総コスト mst_weight に加算します。
   • 辺を昇順に走査しているため、最後に採用した辺のコストが自動的に max_edge_cost（最大コスト）になります。
4. 終了条件: 採用した辺の数が \(N - 1\) 本に達した時点で、すべての拠点が連結された（最小全域木が完成した）ことになるため、探索を終了します。
5. 答えの出力: mst_weight + K * max_edge_cost を計算して出力します。

---

計算量

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

  • 辺のソートに \(O(M \log M)\) 時間かかります。
  • Union-Find の操作（find, union）は、経路圧縮などの最適化により1回あたりほぼ定数時間 \(O(\alpha(N))\) で行えます。全体のループは最大で \(M\) 回回るため、この部分は \(O(M \alpha(N))\) です。
  • したがって、全体の時間計算量はソートがボトルネックとなり \(O(M \log M)\) となり、制約の \(N, M \le 2 \times 10^5\) に対して十分高速に動作します。

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

  • 辺の情報を格納する配列に \(O(M)\)、Union-Find の親を表す配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

• 高速な入出力: Pythonでは入力数が多いため、sys.stdin.read().split() を用いて一括で入力を読み込むことで、入出力のボトルネックを解消しています。

• Union-Findの経路圧縮: find 関数内で親ノードを再帰的に（またはループで）書き換える「経路圧縮」を行うことで、クエリあたりの計算量をほぼ \(O(1)\) に落としています。

• 最大コストの更新: 辺をコストの昇順に処理しているため、新しく採用された辺のコストで max_edge_cost を上書きしていくだけで、最終的に採用された中で最大のコストを正しく保持できます。

  ソースコード

import sys

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])
    
    edges = []
    idx = 3
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        c = int(input_data[idx+2])
        edges.append((c, u, v))
        idx += 3
        
    # コストの昇順にソート
    edges.sort(key=lambda x: x[0])
    
    # Union-Find
    parent = list(range(N + 1))
    
    def find(i):
        path = []
        while parent[i] != i:
            path.append(i)
            i = parent[i]
        for node in path:
            parent[node] = i
        return i

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j
            return True
        return False

    mst_weight = 0
    max_edge_cost = 0
    edges_count = 0
    
    for c, u, v in edges:
        if union(u, v):
            mst_weight += c
            max_edge_cost = c
            edges_count += 1
            if edges_count == N - 1:
                break
                
    ans = mst_weight + K * max_edge_cost
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。