[USACO01OPEN] Earthquake

题目解析

这道题目是一个非常经典的**0/1分数规划（0/1 Fractional Programming）问题，结合了最小生成树（MST）**的知识。

1. 题目分析

我们需要选择一组边，使得这组边构成一个生成树（保证所有牧场连通），并且最大化以下目标函数：

\text{Answer} = \frac{\text{总利润}}{\text{总时间}} = \frac{F - \sum c_i}{\sum t_i}

其中：

$F$ 是约翰支付的总金额（固定值）。
$\sum c_i$ 是所选道路的总成本。
$\sum t_i$ 是所选道路的总施工时间。

2. 数学推导 (分数规划二分法)

我们假设存在一个答案 $x$ ，使得：

\frac{F - \sum c_i}{\sum t_i} \ge x

因为时间 $\sum t_i$ 肯定是正数，我们可以将分母乘过去（不等号方向不变）：

F - \sum c_i \ge x \cdot \sum t_i

移项整理：

F \ge \sum c_i + x \cdot \sum t_i

F \ge \sum (c_i + x \cdot t_i)

这个不等式的含义是：

如果我们要检查是否存在一个比率 $x$ ，我们需要判断是否能找到一组边（构成生成树），使得这组边的 “新权值” 之和小于等于 $F$ 。

这里的“新权值”定义为：对于每一条边 $i$ ，它的权值 $w_i = c_i + x \cdot t_i$ 。

3. 算法设计

根据上面的推导，我们可以确定解题策略：二分答案 + 最小生成树。

二分范围：
- 下界 $L = 0$ （题目要求如果无利可图输出 0.0000）。
- 上界 $R$ ：由于 $F$ 最大为 $2 \times 10^9$ ，时间最小为 1，理论上最大值可能很大，可以设为一个足够大的数（比如 $2 \times 10^9$ 或者 $10^9$ 即可，实际上由于 $c_i \ge 1$ ，且至少 $N-1$ 条边，上界设为 $F$ 也是安全的）。
Check 函数 (check(x))：
- 对于给定的 $x$ ，重新计算每条边的权值： $w_i = c_i + x \cdot t_i$ 。
- 使用 Kruskal 或 Prim 算法求出当前新权值下的**最小生成树（MST）**的总权值 $Sum$ 。
- 判断 $F \ge Sum$ 。
  - 如果成立，说明我们花费的代价比 $F$ 小（或者相等），意味着利润还能更高（或者分母可以更小），所以尝试更大的 $x$ ( $L = mid$ )。
  - 如果不成立，说明这个比率 $x$ 太高了，导致总成本（含时间折算）超过了 $F$ ，需要减小 $x$ ( $R = mid$ )。
为什么是生成树？
- 因为边权 $c_i$ 和 $t_i$ 都是正数，如果不构成树而包含了环，或者选了多余的边，只会增加 $\sum c_i$ 和 $\sum t_i$ ，从而导致分子 $(F - \sum c_i)$ 变小，分母变大，总比值一定变小。所以最优解一定是一个边数最少的连通图，即生成树。

4. 代码实现

使用 Kruskal 算法来实现 MST。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-06 09:20:33
 */
#include <bits/stdc++.h>
#include <iomanip>
#include <ios>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
const int maxe = 4e6+5;
const int mod = 1e9+7;

int n,m,F;
int a[maxn];

//oisnip_begin最小生成树mst_kruskal.cpp
// 定义边的结构体
struct Edge {
    int u, v;
    long long c;
    long long t;
    double val = 0; // c_i + x * t_i , 排序用
    // 重载 < 运算符，方便 std::sort 直接排序
    bool operator<(const Edge& other) const {
        return val < other.val;
    }
};
std::vector<Edge> edges; // 存储所有边

// Kruskal 算法封装结构体
struct KruskalAlgorithm {
    struct DSU {
        std::vector<int> fa;
        // 初始化并查集
        void init(int n) {
            fa.resize(n + 1);
            std::iota(fa.begin(), fa.end(), 0); // 赋值 0, 1, 2... n
        }
        int find(int x) {
            return x == fa[x] ? x : fa[x] = find(fa[x]); // 路径压缩
        }
        bool merge(int x, int y) {
            int fx = find(x), fy = find(y);
            if (fx == fy) return false; // 已经在同一个集合
            fa[fx] = fy;
            return true;
        }
    } dsu;

    int n; // 点的数量

    // 初始化：清空边，设定点数
    void init(int _n) {
        n = _n;
        edges.clear();
        dsu.init(n);
    }

    // 加边函数：心智负担低，不用操心数组下标
    void add_edge(int u, int v, long long c,ll t) {
        edges.push_back({u, v, c,t});
    }

    // 执行算法
    // 返回值：最小生成树的权值和。如果无法连通，返回 -1
    double solve() {
        // 1. 排序：贪心的基础
        std::sort(edges.begin(), edges.end());
        
        // 2. 重新初始化并查集状态（防止多次调用 solve 出错）
        dsu.init(n);

        double ans = 0; // 权值和，注意开 long long
        int cnt = 0;       // 记录选了多少条边

        for (const auto& e : edges) {
            if (dsu.merge(e.u, e.v)) { // 如果不在同一集合，合并
                ans += e.val;
                cnt++;
                // 如果需要输出选中的边，可以在这里打印
                // cout << e.u << " " << e.v << " " << e.w << endl;
            }
            if (cnt == n - 1) break; // 优化：选够了边就退出
        }

        // 3. 连通性检查：如果选的边数少于 n-1，说明图不连通
        if (cnt < n - 1) return -1;
        
        return ans;
    }
} kruskal;
//oisnip_end

bool check(double x) {
    for( auto & e : edges) {
        e.val = e.c + x * e.t;
    }

    double ans = kruskal.solve();
    return F >= ans;

}

void init(){
    std::cin >> n >> m >> F;
    kruskal.init(n);
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        int u,v,c,t;
        std::cin >> u >> v >> c >> t;
        kruskal.add_edge(u,v,c,t);
    }


}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);

    init();
    double l = 0, r = F;

    for(int i = 0 ;i< 100;i++) {
        double mid = (l+r) / 2;
        if( check(mid) )
            l = mid; // 可行
        else
            r = mid;
    }
    std::cout << fixed << setprecision(4) << l << "\n";
    
    return 0;
}

5. 复杂度分析

时间复杂度：
- 二分循环次数固定为 $K$ (例如 100 次)。
- 每次 check 内部包含一次排序和一次并查集遍历。
- 排序复杂度： $O(M \log M)$ 。
- 并查集复杂度： $O(M \alpha(N))$ ，接近线性。
- 总复杂度： $O(K \cdot M \log M)$ 。
- 代入数据： $100 \times 10000 \times 14 \approx 1.4 \times 10^7$ ，在通常 1秒 ( $10^8$ 次运算) 的时限内非常安全。
空间复杂度：
- 存储边 $O(M)$ ，并查集 $O(N)$ 。

6. 注意事项

精度问题：二分浮点数时，推荐使用固定次数循环（如 for(int i=0; i<100; i++)）而不是 while(r-l > eps)，这样可以避免死循环并确保精度足够。
数据类型：虽然 $N, M$ 是整数，但 $F$ 和计算过程中的权值涉及比率，必须使用 double。
负利润处理：题目说如果无利可图输出 0.0000。我们的二分下界设为 0，如果连 $x=0$ 都不满足（即 $\sum c_i > F$ ），二分会自动收敛到 0，符合题意。