概要

すべての拠点を連結にするケーブル集合 \(S\) について、

\[ \sum_{i \in S} c_i + K \times \max_{i \in S} c_i \]

を最小化する問題です。結論として、通常の最小全域木（MST）を求めればよいです。

考察

まず、選ぶケーブル集合 \(S\) は、すべての拠点を連結にする必要があります。

ここで、もし \(S\) に閉路が含まれている場合を考えます。
閉路の中の辺を \(1\) 本取り除いても、グラフは連結のままです。

また、辺のコストはすべて正なので、辺を取り除くと総コストは必ず減ります。
さらに、最大コストの辺も増えることはありません。

したがって、最適解は必ず辺数が \(N-1\) 本の全域木になります。

---

次に、目的関数は単なる総コストではなく、

\[ \text{総コスト} + K \times \text{最大辺コスト} \]

です。

一見すると、総コスト最小の全域木ではなく、最大辺コストも考慮した特別な木を探す必要がありそうです。

しかし、最小全域木（MST）には次の重要な性質があります。

• MST は、総コストが最小である
• MST は、最大辺コストも最小である

後者は「最小ボトルネック全域木」の性質です。

つまり、任意の全域木 \(T\) に対して、MST を \(T_{\text{mst}}\) とすると、

\[ \sum_{e \in T_{\text{mst}}} c_e \leq \sum_{e \in T} c_e \]

かつ

\[ \max_{e \in T_{\text{mst}}} c_e \leq \max_{e \in T} c_e \]

が成り立ちます。

今回、\(K\) は非負整数なので、

\[ K \times \max_{e \in T_{\text{mst}}} c_e \leq K \times \max_{e \in T} c_e \]

も成り立ちます。

よって、

\[ \sum_{e \in T_{\text{mst}}} c_e + K \times \max_{e \in T_{\text{mst}}} c_e \leq \sum_{e \in T} c_e + K \times \max_{e \in T} c_e \]

となり、MST が最適です。

---

素朴にすべてのケーブル集合を試すと、候補は \(2^M\) 通りあり、\(M \leq 2 \times 10^5\) なので到底間に合いません。

また、最大辺コストを固定して毎回全域木を作るような方法も、実装次第では非常に重くなります。

この問題では、MST を一度求めるだけで十分です。

アルゴリズム

クラスカル法を使って最小全域木を求めます。

手順は次の通りです。

1. すべての辺をコスト \(c_i\) の昇順にソートする
2. Union-Find（DSU）を用意する
3. コストが小さい辺から順に見ていく
4. その辺を追加しても閉路ができないなら、MST に採用する
5. 採用した辺について
   • 総コスト sum に \(c_i\) を加える
   • 最大辺コスト mx を更新する
6. 採用した辺数が \(N-1\) 本になったら終了
7. 答えは

\[ \text{sum} + K \times \text{mx} \]

です。

クラスカル法では、コストの小さい辺から順に採用するため、総コスト最小の全域木が得られます。

計算量

• 時間計算量: \(O(M \log M)\)
  • 辺のソートが支配的です
  • Union-Find の操作はほぼ定数時間です
• 空間計算量: \(O(N + M)\)
  • 辺の配列と Union-Find の配列を持ちます

実装のポイント

• 答えは大きくなるため、long long を使います。

  • 例えば \(K \times \max c_i\) は最大で \(10^6 \times 10^6 = 10^{12}\) になります。

• Union-Find では、経路圧縮とサイズによる併合を使うと高速です。

• 入力の頂点番号は \(1\) 始まりなので、実装では \(0\) 始まりに変換しています。

• 採用した辺数が \(N-1\) 本になったら、それ以上見る必要はありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }
    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Edge {
    int u, v, c;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<Edge> edges(M);
    for (auto &e : edges) {
        cin >> e.u >> e.v >> e.c;
        --e.u;
        --e.v;
    }

    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
        return a.c < b.c;
    });

    DSU dsu(N);
    long long sum = 0;
    long long mx = 0;
    int cnt = 0;

    for (const auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            sum += e.c;
            mx = max(mx, (long long)e.c);
            cnt++;
            if (cnt == N - 1) break;
        }
    }

    cout << sum + K * mx << '\n';

    return 0;
}

---

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