読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 350 Slim Span

AOJ ICPC 最小全域木

問題

グラフの全域木の中で、辺の重みの最大値  M と最小値  m の差  M - m が最小となるようなものの  M - m を求めよ。また、全域木が構築できないならばその旨を答えよ。

Slim Span | Aizu Online Judge

制約

頂点数:  2 \leq V \leq 100

辺の本数:  0 \leq E \leq n(n - 1)/2

 i の重み:  0 \lt w_i \leq 10000

グラフは無向単純連結グラフ

解法

最小全域木の気配がする。実際最小全域木で解ける。

まずTLE解として、 m M を全通り試すという方法がある。全域木が構築できた  m, M のうち、差が最小のものが答えである。計算量は、 O(E { w_{max} } ^ 2) である。

ただし辺の重みの最大値を  w_{max} とし、毎回の全域木の構築にDFS等で  O(E) かかるものとした。これでは計算回数が 1012 回程度となりTLEである。

実は、 m を決めると、重みが  m 以上の辺のうちできるだけ重みの小さい辺を使うようにすれば  M - m が最小となる。これは  m 以上の辺のみを使ったときの最小全域木を求めることと同じである*1。そこで最小値  m について全探索し、 m 以上の辺のみを使って最小全域木を構築したときの  M - m の最小値を取っていけばよい。計算量はこれで  O(w_{max} E \log V) となり、計算回数は 108 回程度となった。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
 
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
 
template <typename T>
struct edge {
    int from, to;
    T cost;
    edge(){}
    edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
    bool operator< (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to < e.to : from < e.from) : cost < e.cost;
    }
    bool operator> (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to > e.to : from > e.from) : cost > e.cost;
    }
    void print() {
        cout << from << " " << to << " " << cost << endl;
    }
};
 
template <typename T>
class Prim {
private:
    int n;
    vector<vector<edge<T>>> G;
public:
    Prim(int _n) : n(_n) {
        G.resize(n);
    }
    // undirected
    void addEdge(int u, int v, T c) {
        G[u].emplace_back(u, v, c);
        G[v].emplace_back(v, u, c);
    }
    T calc(int s, int min_cost) {
        T ma_gap = -1;
        vector<bool> visited(n);
        int num_visited = 0;
        priority_queue<edge<T>, vector<edge<T>>, greater<edge<T>>> pq;
        pq.push(edge<T>(-1, s, min_cost));
        while (!pq.empty() && num_visited < n) {
            auto e = pq.top(); pq.pop();
            if (visited[e.to]) continue;
            ma_gap = max(ma_gap, e.cost - min_cost);
            visited[e.to] = true;
            num_visited++;
            for (const auto& ne: G[e.to]) {
                if (!visited[ne.to] && ne.cost >= min_cost) pq.push(ne);
            }
        }
        return (num_visited < n ? 1e9 : ma_gap);
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
 
    int n, m;
    int t = 0;
    while (cin >> n >> m, n) {
        Prim<int> prim(n);
        rep(i, m) {
            int a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            prim.addEdge(a, b, c);
        }
 
        int ans = 1e9;
        const int MAX_W = 10000;
        rep2(min_cost, 1, MAX_W + 1) {
            ans = min(ans, prim.calc(0, min_cost));
        }
 
        cout << (ans == 1e9 ? -1 : ans) << endl;
    }
}

解説を書くたびに、やはり必要性・十分性がよくわかってないという気分になる……。

*1:注意として、逆は必ずしも成り立たない。すなわち、 M - m が最小だからと言って、最小全域木であるわけではない。これは問題文中の図からわかる