Qin Shi Huang's National Road System
感觉这道题和hdu4756很像...
求最小生成树里面删去一边E1 再加一边E2 求该边两顶点权值和除以（最小生成树-E1）的最大值
其中（最小生成树-E1）必须是最小的
先跑一遍prim 跑完之后在最小生成树里面dp
dp[i][j] = i到j的路径中最大的那条边 最小生成树减去dp[i][j]肯定会最小
代码如下
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std; const double inf = 0x3f3f3f3f3f;
const int maxn = ;
struct Point {
double x, y;
int n;
} point[maxn];
struct Edge {
int to;
int next;
} edge[maxn<<];
int n, cnt, head[maxn], pre[maxn];
double dis[maxn][maxn], lowc[maxn], sum, dp[maxn][maxn];
bool vis[maxn];
inline void addedge(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
inline double Distance(const Point& lhs, const Point& rhs) {
return sqrt((lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y));
}
void prim() {
sum = 0.0;
memset(vis, , sizeof(vis));
memset(pre, , sizeof(pre));
for (int i = ; i < n; i++) lowc[i] = dis[][i];
vis[] = true;
for (int i = ; i < n; i++) {
double minc = inf;
int p = -;
for (int j = ; j < n; j++) {
if (!vis[j] && minc > lowc[j]) {
minc = lowc[j];
p = j;
}
}
sum += minc;
vis[p] = true;
addedge(p, pre[p]);
addedge(pre[p], p);
for (int j = ; j < n; j++) {
if (!vis[j] && lowc[j] > dis[p][j]) {
lowc[j] = dis[p][j];
pre[j] = p;
}
}
}
}
void dfs(int u, int root) {
vis[u] = true;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (!vis[v]) {
dp[root][v] = max(dp[root][u], dis[u][v]);
dfs(v, root);
}
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%lf%lf%d", &point[i].x, &point[i].y, &point[i].n);
}
for (int i = ; i < n; i++) {
for (int j = i + ; j < n; j++) {
dis[i][j] = dis[j][i] = Distance(point[i], point[j]);
}
}
memset(head, -, sizeof(head));
cnt = ;
prim();
for (int i = ; i < n; i++) {
memset(vis, ,sizeof(vis));
dfs(i, i);
}
double ans = ;
for (int i = ; i < n; i++) {
for (int j = i + ; j < n; j++) {
double temp = sum - dp[i][j];
temp = (point[i].n + point[j].n) / temp;
ans = max(ans, temp);
}
}
printf("%.2f\n", ans);
}
return ;
}