概要

この問題は、与えられた \(N\) 頂点 \(M\) 本の無向グラフにおいて、すべての頂点を連結にする辺の集合（全域木）のうち、総コストと「採用した辺の最大コストの \(K\) 倍」の和（負荷指数）を最小化する問題です。

考察

一見すると、最大コストを抑えるために総コストを犠牲にするようなトレードオフがあるように思えるかもしれません。しかし、実は通常の最小全域木（MST: Minimum Spanning Tree）を求めるだけで、負荷指数を最小化することができます。

その理由を、負荷指数の式 \(\sum_{i \in S} c_i + K \times \max_{i \in S} c_i\) をもとに考えてみましょう。

1. 最大コストの最小性（ボトルネック全域木） グラフを連結にする全域木のうち、含まれる辺の最大コストを最小化したものを「ボトルネック全域木」と呼びます。グラフ理論の重要な性質として、最小全域木（MST）は常にボトルネック全域木でもあるという事実があります。 つまり、どのような全域木を選んでも、その最大コストをMSTの最大コスト（これを \(M_{mst}\) とします）未満にすることはできません。

2. 総コストの最小性 MSTは定義通り、すべての全域木の中で総コスト \(\sum_{i \in S} c_i\) を最小化するものです。

3. 両者の両立 もし最大コストを \(M_{mst}\) より大きくした全域木 \(S'\) を選んだとします。このとき、

   • 最大コストの項 \(K \times \max_{i \in S'} c_i\) は、MSTにおける \(K \times M_{mst}\) 以上になります。
   • 総コストの項 \(\sum_{i \in S'} c_i\) も、MSTの総コスト以上になります。

したがって、最大コストをMSTより大きくしても、負荷指数のどちらの項も改善（減少）することはありません。また、最大コストを \(M_{mst}\) 未満にすることは不可能です。

以上のことから、通常の最小全域木を構成する辺の集合が、常に負荷指数を最小化することが分かります。

アルゴリズム

最小全域木を求める代表的な手法であるクラスカル法（Kruskal’s algorithm）を使用します。

1. すべての辺をコスト \(c_i\) の昇順にソートします。
2. 頂点間の連結関係を高速に管理するために Union-Find（DSU） データ構造を用意します。
3. コストの小さい辺から順に見ていき、その辺を結ぶ2つの頂点がまだ非連結であれば、その辺を全域木に採用し、Union-Findで連結（マージ）します。
4. 採用した辺の数が \(N-1\) 本になった時点で、すべての頂点が連結となり、最小全域木が完成します。
5. 採用した辺の総コスト total_cost と、最後に採用した辺のコスト（＝採用した中で最大コスト） max_cost を用いて、total_cost + K * max_cost を計算し出力します。

計算量

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

  • 辺のソートに \(O(M \log M)\) かかります。
  • Union-Findの各操作（same, merge）はアッカーマン関数の逆関数 \(\alpha(N)\) を用いてほぼ定数時間 \(O(\alpha(N))\) で行えるため、ループ全体の処理は \(O(M \alpha(N))\) です。
  • 全体としてソートがボトルネックとなり、時間計算量は \(O(M \log M)\) となります。これは制約 \(M \le 2 \times 10^5\) に対して十分高速に動作します。

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

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

実装のポイント

• 1-indexed から 0-indexed への変換 入力される頂点番号は \(1\) から \(N\) ですが、プログラム内部やUnion-Findで扱いやすくするために、入力を受け取る際に 1 を引いて \(0\) から \(N-1\) に変換しておきます。

• オーバーフローへの対策 コストの総和や負荷指数は非常に大きな値になる可能性があります（最大で約 \(2 \times 10^5 \times 10^6 + 10^6 \times 10^6 \approx 10^{12}\)）。C++ではオーバーフローを防ぐために、これらの計算や変数には long long 型を使用します。

• AtCoder Library (ACL) の活用 atcoder/dsu を使用することで、Union-Findをバグなく簡潔に実装することができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

struct Edge {
    int u, v;
    long long c;
    bool operator<(const Edge& other) const {
        return c < other.c;
    }
};

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
        edges[i].u--; // 0-indexed に変換
        edges[i].v--;
    }

    // 辺をコストの昇順にソート
    sort(edges.begin(), edges.end());

    dsu d(N);
    long long total_cost = 0;
    long long max_cost = 0;
    int edges_count = 0;

    for (const auto& edge : edges) {
        if (!d.same(edge.u, edge.v)) {
            d.merge(edge.u, edge.v);
            total_cost += edge.c;
            max_cost = max(max_cost, edge.c);
            edges_count++;
            if (edges_count == N - 1) {
                break;
            }
        }
    }

    long long ans = total_cost + K * max_cost;
    cout << ans << "\n";

    return 0;
}

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