概要

木構造の地図を \(2\) 種類以上の色で塗り分け、隣接する区画間の違和感コストの合計を最小化する問題です。

考察

まず、違和感コストの合計は \(W_i \times |a - b|\) の和で計算されます。もしここに「\(2\) 種類以上の色を使わなければならない」という制約がなければ、すべての区画を同じ色で塗ることで違和感コストを \(0\) にできます。

しかし、今回は \(2\) 種類以上の色を使う必要があります。つまり、少なくとも \(1\) 箇所で色を変える必要があります。違和感コストをなるべく小さくするためには、「色を変える箇所を最小限にし、かつ色の番号の差を最小にする」のがよいでしょう。

地図は木構造であるため、\(1\) つの辺を切断すると \(2\) つの部分木に分かれます。そこで、ある \(1\) つの辺 \((u, v)\) を選び、\(u\) 側の部分木をすべて色 \(1\) で、\(v\) 側の部分木をすべて色 \(2\) で塗ることを考えます。このとき、色 \(1\) と色 \(2\) の両方が使われているため \(2\) 色以上使うという条件を満たします。

この塗り方では、色が変わるのは選んだ \(1\) つの辺 \((u, v)\) のみであり、他の辺は両端が同じ色になるため違和感コストは \(0\) になります。選んだ辺 \((u, v)\) のコストは \(W_i \times |1 - 2| = W_i \times 1 = W_i\) となります。

したがって、違和感コストの合計は選んだ辺の重み \(W_i\) そのものとなり、これを最小化するにはすべての辺の中で最も重み \(W\) が小さい辺を選べばよいことが分かります。

アルゴリズム

入力として与えられる \(M\) 個の辺の重み \(W_i\) の中から最小値を探し、それをそのまま出力します。隣接する区画同士の情報（\(u_i, v_i\)）や色の種類数 \(K\) は、最小値を求める過程では直接使用しません。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 重み \(W\) は long long 型で受け取るようにすると安全です。

• 最小値を探す際は、初期値を十分に大きな値（例えば std::numeric_limits<long long>::max() など）に設定しておきます。

  ソースコード

#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    long long K;
    cin >> N >> M >> K;
    long long min_w = numeric_limits<long long>::max();
    for (int i = 0; i < M; ++i) {
        int u, v;
        long long W;
        cin >> u >> v >> W;
        if (W < min_w) {
            min_w = W;
        }
    }
    cout << min_w << endl;
    return 0;
}

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