解法

二分探索。最小全域木。\(N \le M\)として\(O(M \log M \cdot \log \max C_i)\)。

グラフを連結にする\(E' \subseteq E\)の中での\(\sum _ {i \in E} C_i / \sum _ {i \in E} T_i\)の最小値を求める問題。 この答えの値を二分探索。 仮にこれを$a$と置くと \(\sum _ {i \in E} C_i - a \sum _ {i \in E} T_i\) を最小化する問題になって、これは通常の最小全域木問題とほぼ同様に解ける。 不要な辺でも重みが負なら使う点のみが差分。 そうして得られた値$a’$と仮に置いた値$a$の大小を比較すれば、真の値が$a$より大きいか小さいかが分かる。

メモ

  • ARCのDにしては簡単 600点ぐらい
  • 必要十分なコストの形がよく分からない。線形ならというわけではなく、すべての重みの総乗を最小化とかでも同様にできるなどがある

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

struct union_find_tree {
    vector<int> data;
    union_find_tree() = default;
    explicit union_find_tree(size_t n) : data(n, -1) {}
    bool is_root(int i) { return data[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); }
    int tree_size(int i) { return - data[find_root(i)]; }
    int unite_trees(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (tree_size(i) < tree_size(j)) swap(i,j);
            data[i] += data[j];
            data[j] = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

template <typename UnaryPredicate>
double binsearch_float(double l, double r, UnaryPredicate p) {
    assert (l <= r);
    REP (iteration, 100) {
        double m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}


struct edge_t { int u, v, num, den; };

// Kruskal's method
pair<ll, ll> minimum_spanning_tree(int n, vector<edge_t> & edges, double ans) {
    sort(ALL(edges), [&](edge_t const & a, edge_t const & b) {
        return (a.num - ans * a.den) < (b.num - ans * b.den);
    });
    ll num = 0;
    ll den = 0;
    union_find_tree uft(n);
    for (auto e : edges) {
        if (e.num < ans * e.den or not uft.is_same(e.u, e.v)) {
            uft.unite_trees(e.u, e.v);
            num += e.num;
            den += e.den;
        }
    }
    return make_pair(num, den);
}

double solve(int n, int m, vector<edge_t> & edges) {
    return binsearch_float(0, 1e6, [&](double ans) {
        ll num, den; tie(num, den) = minimum_spanning_tree(n, edges, ans);
        return num < ans * den;
    });
}

int main() {
    int n, m; cin >> n >> m;
    vector<edge_t> edges(m);
    REP (i, m) {
        int a, b, c, t; cin >> a >> b >> c >> t;
        edges[i] = { a, b, c, t };
    }
    double ans = solve(n, m, edges);
    printf("%.12lf\n", ans);
    return 0;
}