Luogu 4951 [USACO 2001 OPEN]地震

水个博客玩。

$01$分数规划。

题目要求$\frac{F - \sum_{i = 1}^{n}C_i}{T_i}$最大，设$\frac{F - \sum_{i}C_i}{T_i} \geq e$，移项一下可以得到$F - \sum_{i }(e * T_i + C_i) \geq 0$。

那么在外层二分一个$e$，然后把所有边的权值设成$e * T_i + C_i$做最小生成树，假设这样子生成树的权值为$res$，如果$F - res > 0$ 那么说明答案还可以更大，否则更小。

时间复杂度$O(mlogmlogn(MaxInt))$。

Code：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef double db;

const int N = ;

const int M = ;

const db eps = 1e-;

const db inf = 1e10;

int n, m, ufs[N];

ll cur;

struct Pathway {

    int u, v;

    ll c, t;

    db val;

    friend bool operator < (const Pathway &x, const Pathway &y) {

        return x.val < y.val;

    }

} pat[M];

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

int find(int x) {

    return x == ufs[x] ? x : ufs[x] = find(ufs[x]);

}

inline bool chk(db mid) {

    for(int i = ; i <= m; i++)

        pat[i].val = mid * pat[i].t + 1.0 * pat[i].c;

    sort(pat + , pat +  + m);

    for(int i = ; i <= n; i++) ufs[i] = i;

    int cnt = ; db res = ;

    for(int i = ; i <= m; i++) {

        int u = find(pat[i].u), v = find(pat[i].v);

        if(u == v) continue;

        ufs[u] = v;

        ++cnt;

        res += pat[i].val;

        if(cnt >= n - ) break;

    }

    return (1.0 * cur - res) > ;

}

int main() {

    read(n), read(m), read(cur);

    for(int i = ; i <= m; i++)

        read(pat[i].u), read(pat[i].v), read(pat[i].c), read(pat[i].t);

    db ln = 0.0, rn = inf, mid, res = 0.0;

    for(; ln + eps <= rn; ) {

        mid = (ln + rn) * 0.5;

        if(chk(mid)) ln = mid, res = mid;

        else rn = mid;

    }

    printf("%.4f\n", res);

    return ;

}

巴特西

Luogu 4951 [USACO 2001 OPEN]地震

最新文章

热门文章