题目分析

在一个图中，选择一些边，使得n个点可以联通且所选择的边的单位时间的利润最大。

一般化解法

让我们先来看一个类似问题的一般化解法。

1，什么是0/1分数规划问题！

0/1分数规划的模型是指给定整数a1，a2……an以及b1，b2……bn，求一组解xi（xi=0或者xi=1，1≤i≤n），使得下列式子的值最大。
$$\frac{\sum ai\ast xi}{\sum bi\ast xi}$$
通俗地说，就是给定n对整数ai, bi，从中选出若干对，使选出的数对的ai之和与bi之和的商最大。

2， 0/1分数规划问题求解！

【关键点】 我们无法直接计算$$max\frac{\sum ai}{\sum bi}$$但可以通过二分答案来不断逼近得到它。
——————

回到P4951 [USACO01OPEN] Earthquake一题中来看

【题目大意】 给定n个点，m条双向边，总共的收益是f，但修建每条边有成本ci和时间ti。选择一些边，使得总收益最大，且图连通。

图联通：即所有点都相通，此乃生成树！

且最大化$$\frac{f-\sum ci\ast xi}{\sum ti\ast xi}（xi=0或者xi=1）$$

——————

具体而言：

(1)变形为不等式

猜测一个L，将式子进行变形：
$$\frac{f-\sum ci\ast xi}{\sum ti\ast xi}\ge L$$
两边乘以分母:
$$f-\sum (ci\ast xi)\ge L\ast \sum (ti\ast xi)$$
移项得：
$$f-\sum (ci+L\ast ti)xi\ge 0$$
令wi=ci+L*ti，则问题转化为:
是否存在生成树，使得$$f-\sum wi\ast xi\ge 0$$

(2) 最小化∑wi*xi

需 f-∑wi * xi≥0 ，即可最小化 ∑wi * xi（xi=0或xi=1，即用xi来决定边选与不选）；

此公式的含义为：选择能够将n个点联通的边，且其边权之和最小；

为了尽可能满足最小化∑wi* xi，我们选择最小生成树；

如果最小生成树都无法满足足∑wi* xi≥0 ，那么其他生成树更不可能满足。

(3)重构边权、构建最小生成树

边权修改为wi=(ci+L*ti)，基于新的边权求最小生成树

（4）二分判定逼近答案

若f-∑(ci+L*ti)xi≥0，则令L=mid，寻找更大的L，否则令r=mid。
当二分结束时，mid就是本题的答案。

代码实现

	#include <bits/stdc++.h>
	using namespace std;
	const int N = 405;
	const int M = 1e4 + 5;
	struct edge {
		int u, v, c, t;
		double x;//x是double类型 
	} e[M];
	int n, m, f, fa[N];
	//寻找祖先 
	int get(int x) {
		if (x == fa[x]) return x;
		return fa[x] = get(fa[x]);
	}
	//合并 
	void merge(int x, int y) {
		fa[get(x)] = get(y);
	}
	//根据0/1分数规划推出新的边权 
	bool cmp(edge a, edge b) {
		return a.c + a.x * a.t < b.c + b.x * b.t;
	}
	 
	bool check(double x) {
		for (int i = 1; i <= m; i++) e[i].x = x;
		sort(e + 1, e + m + 1, cmp);
		for (int i = 1; i <= n; i++) fa[i] = i;
		int cnt = 0;
		double tot = 0;
		//计算最小生成树 
		for (int i = 1; i <= m; i++) { 
			if (get(e[i].u) != get(e[i].v)) {
				merge(e[i].u, e[i].v);
				tot += e[i].c + x * e[i].t;
			}
		}
		return tot <= f;
	}
	 
	int main() {
		cin >> n >> m >> f;
		for (int i = 1; i <= m; i++) {
			cin >> e[i].u >> e[i].v >> e[i].c >> e[i].t;
		}
		double l = 0, r = 1e10;
		while (r - l > 1e-6) {
			double mid = (l + r) / 2;
			if (check(mid)) l = mid;
			else r = mid;
		}
		printf("%.4f", l);
		return 0;
	}