概要

すべての拠点を連結にするケーブル集合のうち、「総コスト \(+ K \times\) 最大コスト」を最小化する問題です。これは最小全域木（MST）を求めることで解けます。

考察

連結にするだけなら木で十分

すべての拠点を連結にするには、辺の集合 \(S\) が全域木（\(N-1\) 本の辺で全頂点をつなぐ木）であれば十分です。サイクルを含む余分な辺を加えても、総コスト \(\sum c_i\) は増えるだけで、最大コスト \(\max c_i\) も減ることはありません。したがって、負荷指数を最小化する \(S\) は必ず木の形になります。よって候補は「全域木」に絞れます。

負荷指数の2つの項を同時に最小化できるか

負荷指数は次の2項からなります。

\[ \left(\sum_{i \in S} c_i\right) + K \times \max_{i \in S} c_i \]

一見すると「総コストを下げる」ことと「最大コストを下げる」ことは別々の最適化に見え、トレードオフがあるように思えます。しかしここで重要な事実があります。

• 最小全域木（MST）は総コスト \(\sum c_i\) を最小にする。
• MST は同時に「最大辺コストを最小にする全域木（最小ボトルネック全域木）」でもある。

2つ目の性質は重要です。実は、MST に含まれる辺の最大コストは、すべての全域木の中で取りうる最大コストの最小値に一致します（最小ボトルネック全域木の性質）。

つまり、MST は \(\sum c_i\) と \(\max c_i\) の両方を同時に最小化しています。したがって、両者を足し合わせた負荷指数も MST で最小になります。トレードオフを心配する必要はありません。

素朴なアプローチの問題点

全域木をすべて列挙して負荷指数を比較する、といった方法は全域木の数が指数的に膨大になるため不可能です。上記の考察により、単に MST を1つ求めればよいと分かります。

アルゴリズム

クラスカル法で最小全域木を構築します。

1. すべての辺をコスト \(c_i\) の昇順にソートする。
2. コストの小さい辺から順に見て、Union-Find（DSU）を使って「その辺の両端がまだ連結でなければ採用する」ことを繰り返す。
3. 採用した辺数が \(N-1\) になったら全域木が完成。

このとき、 - \(\text{sum}\) ＝ 採用した辺のコストの総和 - \(\text{maxc}\) ＝ 採用した辺のコストの最大値

を記録します。辺を昇順に処理しているので、最後に採用した辺のコストが最大値になります。

最終的な答えは

\[ \text{ans} = \text{sum} + K \times \text{maxc} \]

です。

具体例

例えば 3 頂点で辺が \((1,2,c=2),\ (2,3,c=3),\ (1,3,c=5)\)、\(K=2\) の場合： - MST はコスト \(2\) と \(3\) の辺を採用し、\(\text{sum}=5\)、\(\text{maxc}=3\)。 - 負荷指数 \(= 5 + 2 \times 3 = 11\)。

コスト \(5\) の辺を使う全域木より小さくなることが確認できます。

計算量

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

実装のポイント

• 辺を {c, u, v} の順で配列に格納すると、sort でコスト昇順に並びます。

• 昇順処理なので、採用した最後の辺のコストをそのまま maxc に上書きしていけば最大値が得られます（毎回 max を取る必要すらありません）。

• \(c_i \le 10^6\)、\(N \le 2\times10^5\)、\(K \le 10^6\) より総和や \(K \times \text{maxc}\) は 32bit を超え得るので、long long（64bit整数）で計算します。

• Union-Find は経路圧縮とランク（またはサイズ）による併合を入れて高速化します。

  ソースコード

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

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

int main(){
    int N, M; long long K;
    scanf("%d %d %lld", &N, &M, &K);
    vector<array<long long,3>> edges(M); // c, u, v
    for(int i=0;i<M;i++){
        long long u,v,c;
        scanf("%lld %lld %lld", &u, &v, &c);
        edges[i] = {c, u-1, v-1};
    }
    sort(edges.begin(), edges.end());
    DSU dsu(N);
    long long sum = 0, maxc = 0;
    int cnt = 0;
    for(int i=0;i<M && cnt<N-1;i++){
        long long c = edges[i][0];
        int u = (int)edges[i][1], v = (int)edges[i][2];
        if(dsu.unite(u,v)){
            sum += c;
            maxc = c; // 昇順なので最後が最大
            cnt++;
        }
    }
    long long ans = sum + K * maxc;
    printf("%lld\n", ans);
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。