「USACO2001OPEN」地震

有一只施工队要修路，每条路有成本 \(c\) 和需要的时间 \(t\) ，总收入为 \(f\) ，要求选择数条边使图联通，求 \(f-\frac{\sum{c_i*x_i}}{\sum{t_i*x_i}}=ans\) 的最大值 ( \(x_i\) 为 \(0\) 或 \(1\) 表示选或不选）

Luogu

分析

我们设答案为 \(k\) ，则有
\[\frac{f-\sum{c_i}}{\sum{t_i}}=k\]
移项得
\[f-(\sum{c_i}+k*\sum{t_i})=0\]
也就是
\[f-\sum{(c_i+k*t_i)}=0\]
我们设
\[f(k)=f-\sum(c_i+k*t_i)\]
当 \(f(k)>0\) 时，则有比 \(k\) 更好的答案；当 \(f(k)=0\) 时， \(k\) 一定是最优解；而当 \(f(k)<0\) 时， 答案要小于 \(k\) 。

所以我们可以二分枚举 \(k\) 值，设 \(v_i=c_i+k*t_i\) ，每条边按 \(v\) 从小到大排序，每次用 Kruskal 求出最小生成树，计算 \(\sum{v_i}\) ，判断其是否小于等于 \(f\) 即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 401
#define M 10003
#define eps 1e-7
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

struct edge {
    int u, v, c, t;
    double w;
    friend bool operator < (edge x, edge y) { return x.w < y.w; }
} e[M];

int n, m, f, cnt;
int fa[N];

int find(int x) { return fa[x] == x ? x : find(fa[x]); }

double Kruskal() {
    double res = 0; cnt = 0;
    sort(e + 1, e + 1 + m);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int f1 = find(e[i].u), f2 = find(e[i].v);
        if (f1 == f2) continue;
        fa[f2] = f1; res += e[i].w;
        if (++cnt == n - 1) break;
    }
    return res;
}

bool check(double t) {
    for (int i = 1; i <= m; ++i) e[i].w = e[i].c + e[i].t * t;
    return Kruskal() <= (double)f;
}

int main() {
    int u, v, c, t;
    read(n), read(m), read(f);
    for (int i = 1; i <= m; ++i)
        read(e[i].u), read(e[i].v), read(e[i].c), read(e[i].t);
    double l = 0, r = 1000000000.0;
    while (r - l > eps) {
        double mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.4lf", l);
    return 0;
}

「USACO2001OPEN」地震

原文：https://www.cnblogs.com/hlw1/p/12260548.html