概要

与えられた無向グラフの全域木のうち、「辺のコストの総和」と「最大の辺のコスト \(\times K\)」の和である「負荷指数」を最小化する問題です。

考察

負荷指数は、選ぶ辺の総和 \(\sum c_i\) に、最大コスト \(\max c_i\) を \(K\) 倍したものを足した値です。 ここで、採用する辺の最大コストを \(X\) と固定して考えてみます。最大コストが \(X\) であるということは、使える辺がコスト \(X\) 以下の辺のみに限定されるということです。 この制約のもとで全域木を構築しようとした場合、総コストを最小にするためにはコスト \(X\) 以下の辺を使って最小全域木（MST）を構築すればよいことがわかります。

すべての頂点を連結にするための最大コスト \(X\) の候補として、入力で与えられる辺のコスト \(c_i\) をすべて試すことを考えます。 辺をコストの小さい順にソートし、クラスカル法のように小さい順に辺を追加していきます。こうすることで、あるコスト \(X\) まで辺を追加した時点での「使用した辺の総和」は、まさに「コスト \(X\) 以下の辺のみで構築したときの最小全域木のコスト」になります。 グラフ全体が初めて連結になった瞬間の最大コスト \(X\) を用いたとき、負荷指数 \(\text{mst\_sum} + K \times X\) が最小値になります。なぜなら、それ以上コストの大きい辺を追加して得られる最大コスト \(X'\) では、総和は変わらないか増加し、かつペナルティ項 \(K \times X'\) も増加してしまうため、解が良くなることはないからです。

アルゴリズム

1. 辺をコストの昇順にソートします。
2. Union-Find木を初期化し、辺の総コスト mst_sum = 0 で用意します。
3. 同じコストの辺ごとにまとめて処理します。まとまった範囲の辺で、まだ非連結な頂点同士を結ぶものがあれば、Union-Findで結合し、そのコストを mst_sum に加算します。
4. そのコストの辺の処理が終わった後、グラフ全体が連結（すべての頂点が同じグループ）になっているかを確認します。
5. 連結になっていた場合、そのときの「mst_sum + K \(\times\) 現在の辺のコスト」が負荷指数の最小値となるので、これを出力して終了します。

計算量

• 時間計算量: \(O(M \log M + M \alpha(N))\)。ソートに \(O(M \log M)\)、Union-Findの操作に \(O(M \alpha(N))\) かかります。
• 空間計算量: \(O(N + M)\)。グラフの情報とUnion-Find木を保持するために必要です。

実装のポイント

同じコストの辺をまとめて処理することが重要です。もし同じコストの辺を1本ずつ追加して途中で連結判定を行うと、同じ最大コストに対して複数回判定を行うことになりロジックが複雑になります。特定のコストの辺をすべて追加し終えたタイミングで連結判定を行うことで、簡潔に実装できます。 また、\(N\) と \(M\) が大きいため、入力の高速化（ios_base::sync_with_stdio(false) など）や、答えが64bit整数に収まるかの確認（long long 型の使用）に注意してください。

ソースコード

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

using namespace std;
using namespace atcoder;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    long long K;
    cin >> N >> M >> K;
    
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c;
        edges[i].u--;
        edges[i].v--;
    }
    
    sort(edges.begin(), edges.end());
    
    dsu d(N);
    long long mst_sum = 0;
    long long ans = 4e18;
    
    for (int i = 0; i < M; ) {
        int j = i;
        while (j < M && edges[j].c == edges[i].c) {
            if (!d.same(edges[j].u, edges[j].v)) {
                d.merge(edges[j].u, edges[j].v);
                mst_sum += edges[j].c;
            }
            j++;
        }
        if (d.size(0) == N) {
            ans = min(ans, mst_sum + K * edges[i].c);
            break;
        }
        i = j;
    }
    
    cout << ans << "\n";
    return 0;
}

この解説は or-glm5.2-high によって生成されました。