2126번: 지진

https://www.acmicpc.net/problem/2126


$O(cm\lg m)$

시간당 최대 이득이 x이상인가를 확인하는 결정 문제로 바꿔보자.
mst를 이루는 간선들의 (ci,ti)에 대해
{f-sum(ci)}/sum(ti) >= x
정리하면 f>=sum(ci+ti*x)
우변은 잘 알려진 프림, 크루스칼 알고리즘을 통해 최솟값을 구할 수 있다.

이제 파라메트릭 서치를 할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 400, MXM = 1e4;
struct st {
    int u, v, c, t;
}e[MXM];
int n, m, f, p[MXN + 1];
double low, up, mid;
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
bool mst() {
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(e, e + m, [](st i, st j) {return i.c + i.t*mid < j.c + j.t*mid; });
    double s = 0;
    for (int i = 0; i < m; i++) if (par(e[i].u) ^ par(e[i].v)) {
        p[par(e[i].u)] = par(e[i].v);
        s += e[i].c + e[i].t*mid;
    }
    return s <= f;
}
int main() {
    scanf("%d%d%d", &n, &m, &f);
    for (int i = 0; i < m; i++) scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].c, &e[i].t);
    up = f;
    for (int i = 0; i < 100; i++) {
        mid = (low + up) / 2;
        mst() ? low = mid : up = mid;
    }
    printf("%.4lf", mid);
    return 0;
}