AtCoder ARC 026 D - 道を直すお仕事 (試験管黄色)

「平均値の最小化」に基づく二分探索 + 最小全域問題

• 問題へのリンク

問題概要 (意訳)

頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。

グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのような辺集合について、各辺の (重みの総和) を (長さの総和) で割った値の最小値を求めよ。

制約

• 

考えたこと

「平均値の最小化」なので、二分探索法がばっちりはまる。(重みの総和) / (長さの総和) を 以下にできるかどうかを判定する問題は、結局次のような問題になる。

---

• 各辺 の重みを とする
• 辺集合であって、すべての頂点を連結にするものについて、重み の総和が 0 以下となるようにできるかを判定せよ

---

この問題は Kruskal 法とほとんど同様に解ける。重みが小さい辺から順にみていき、「その両端が非連結」または「辺の重みが負」の場合にその辺を採用していけばよい。

計算量は、二分探索法の反復回数を として、 となる。

コード

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

// Union-Find
struct UnionFind {
    // core member
    vector<int> par;

    // constructor
    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        map<int, vector<int>> groups;
        for (int i = 0; i < uf.par.size(); ++i) {
            int r = uf.root(i);
            groups[r].push_back(i);
        }
        for (const auto &it : groups) {
            s << "group: ";
            for (auto v : it.second) s << v << " ";
            s << endl;
        }
        return s;
    }
};

struct Edge {
    int from, to;
    double weight;
    Edge(){}
    Edge(int f, int t, double w) : from(f), to(t), weight(w) {}
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    vector<double> C(M), T(M);
    for (int i = 0; i < M; ++i) cin >> A[i] >> B[i] >> C[i] >> T[i];
    
    double low = 0.0, high = 1LL<<50;
    for (int _ = 0; _ < 100; ++_) {
        double x = (low + high) / 2;
        
        // 辺を C[i] - x T[i] が小さい順に
        vector<Edge> edges(M);
        for (int i = 0; i < M; ++i) {
            edges[i] = Edge(A[i], B[i], C[i] - x * T[i]);
        }
        sort(edges.begin(), edges.end(), [&](Edge a, Edge b){return a.weight < b.weight;});
        
        // Union-Find
        double res = 0.0;
        UnionFind uf(N);
        for (auto e : edges) {
            if (!uf.same(e.from, e.to) || e.weight < 0) {
                res += e.weight;
                uf.merge(e.from, e.to);
            }
        }
        if (res <= 0) high = x;
        else low = x;
    }
    cout << fixed << setprecision(10) << high << endl;
}