「Solution」秦始皇的国道

最小生成树

思路

要使$A/B$最大化。就要想办法让$A$尽量大，同时让$B$变小。

先考虑让$B$变小。那么可以想到在保证连通性的情况下最小生成树的权长肯定最小。

所以先跑一遍Kruskal或Prime求出最小生成树。

然后枚举最小生成树上的边，考虑删掉，即在余下的边上换上一条魔道。

如果最小生成树如上图。

那么删掉一条边之后，它会分裂成两棵子树。

为了使它联通并让魔道两边的城市的人口最多。则要在两棵子树中分别找到人口最多的那个节点，再将找到的两个节点连起来作为魔道，去更新答案即可。

Code

#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int MAXM = MAXN * MAXN + 5;
int t, n, m, fa[MAXN], u[MAXN], v[MAXN], cnt;
double len, ans;
vector<int> G[MAXN];
bool vis[MAXN];
struct node {
	double x, y;
	int p;
} c[MAXN];
struct edge {
	int u, v;
	double w;
	edge(){}
	edge(int U, int V, double W) {
		u = U, v = V, w = W;
	}
} dis[MAXM];
bool cmp(edge x, edge y) {
	return x.w < y.w;
}
double dist(int x, int y) {
	return sqrt((c[x].x - c[y].x) * (c[x].x - c[y].x) + (c[x].y - c[y].y) * (c[x].y - c[y].y));
}
int FindSet(int v) {
	if (fa[v] == v) return fa[v];
	else return fa[v] = FindSet(fa[v]);
}
bool UnionSet(int u, int v) {
	int x = FindSet(u), y = FindSet(v);
	if (x == y) return 0;
	fa[x] = y;
	return 1;
}
void Kruskal() {
	for (int i = 1; i <= n; i++) fa[i] = i;
	sort (dis + 1, dis + 1 + m, cmp);
	cnt = 0, len = 0;
	for (int i = 1; i <= m; i++) {
		if (UnionSet(dis[i].u, dis[i].v)) {
			len += dis[i].w, u[++cnt] = dis[i].u, v[cnt] = dis[i].v;
			G[dis[i].u].push_back(dis[i].v), G[dis[i].v].push_back(dis[i].u);
		}
	}
}
void dfs(int u, int& val) {
	vis[u] = 1;
	val = max(c[u].p, val);
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v] == 1) continue;
		dfs(v, val);
	}
}
int main() {
	scanf ("%d", &t);
	while (t--) {
		scanf ("%d", &n);
		m = 0, ans = 0;
		for (int i = 1; i <= n; i++) {
			scanf ("%lf %lf %d", &c[i].x, &c[i].y, &c[i].p);
			G[i].clear();
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dis[++m] = edge(i, j, dist(i, j));
			}
		}
		Kruskal();
		for (int i = 1; i <= cnt; i++) {
			memset(vis, 0, sizeof(vis));
			vis[v[i]] = 1;
			int a = 0, tmp = 0;
			dfs(u[i], tmp);
			a += tmp;
			memset(vis, 0, sizeof(vis));
			vis[u[i]] = 1;
			tmp = 0;
			dfs(v[i], tmp);
			a += tmp;
			double now = a * 1.0 / (len - dist(u[i], v[i]));
			ans = max(ans, now);
		}
		printf ("%.2lf\n", ans);
	}
	return 0;
}