点这里
题意： 给定n个城市，每个城市都有一个坐标和人数。现要将所有的城市连接起来，花费为两个城市之间的距离。你可以将其中的一条路的花费，变为零，称其为魔法道路。假设A为魔法道路连接的两个城市的总人口，B为在这条魔法道路的基础上，连接所有城市的最小花费；要求输出最大的A / B。 题解： 看上去好像是先构造出最小生成树，得到没有魔法道路下的最小花费，然后逐个去删边，去求每种情况下的A和B，最后拿到最大值。整理一下思路
构造最小生成树： 构造的是没有魔法道路下的最小生成树，
先用Kruskal求得在没有魔法道路下，连接所有城市的最小花费。删边： 生成一条魔法道路可以节省一条路的花费，转化过来，就相当于从最小生成树中删除了某条边。因此，我们应该
从最小生成树上去枚举删除每一条边的情况，而不是全图枚举。魔法道路 ？= 删除的边： 生成一条魔法道路，对我们的最小生成树的直观影响，就是可以少连一条边。但是，魔法道路必须是最小生成树上的边吗？可能我这么一说，大家就会觉得我前后矛盾了。 看这样一个例子：假设我们构造出来的最小生成树如下1->2->3->4，再假设我在城市1和城市4之间，生成了一条魔法道路，那么此时我们的最小生成树就有可能变成1->2->3以为1和4之间已经有一条魔法道路了，不需要我们另外修路。这种情况下，我们的确从最小生成树上删边了，但是删的，却不是我们的魔法道路。魔法道路两端的总人口A： 再明确一条看似很矛盾的问题：
我们要从最小生成树上删的边 ≠ 魔法道路 但是我们要求的总人口A确是魔法道路两端的城市，怎么办？既然我们一开始就选择了用Kruskal的算法来构造最小生成树，那么在这里，仍然可以用到并查集的思想。将与魔法道路一端的城市u连通的城市划分为一个集合T，与另一端城市v连通的城市划分到另一个集合S。那么我们想要的总人口A = 集合T中的最大值 + 集合S中的最大值。
过程中犯的错：
应该删最小生成树上的边 && 删边 ≠ 魔法道路 我一开始确实是枚举删最小生成树上的边，但是样例就没通过，原因再上面第三条就有解释，最理想的魔法道路可能本来就不在最小生成树上。然后我就去枚举删全图的边，全图，可想而知，结果只能是TLE，我还顽固地又加上了很多剪枝。直到我意识到删边 ≠ 魔法道路才能解决这个问题。
#include<bits/stdc++.h>
using namespace std
;
const int N
= 1e3 + 10;
int T
, n
, t
;
int s
[N
];
double ans
;
struct node
{ int id
, x
, y
, w
;} g
[N
];
struct edge
{ int u
, v
, w
;double len
;} e
[500 * N
];
vector
<edge
> V
;
bool cmp(edge a
, edge b
){ return a
.len
< b
.len
;}
bool compare(node a
, node b
){ return a
.w
> b
.w
;}
int find(int x
){ return s
[x
] == x
? x
: s
[x
] = find(s
[x
]);}
double len(int i
, int j
){
double x
= g
[i
].x
- g
[j
].x
, y
= g
[i
].y
- g
[j
].y
;
return sqrt(x
* x
+ y
* y
);
}
void kruskal(){
for(int i
= 1; i
<= n
; i
++) s
[i
] = i
; V
.clear();
sort(e
, e
+ t
, cmp
);
for(int i
= 0; i
< t
; i
++){
int u
= find(e
[i
].u
), v
= find(e
[i
].v
);
if(u
== v
) continue;
s
[v
] = u
;
ans
+= e
[i
].len
;
V
.push_back(e
[i
]);
}
}
void solve(){
double maxn
= 0;
sort(g
+ 1, g
+ n
+ 1, compare
);
for(int i
= 0; i
< V
.size(); i
++){
for(int j
= 1; j
<= n
; j
++) s
[j
] = j
;
for(int j
= 0; j
< V
.size(); j
++){
if(i
== j
) continue;
int u
= find(V
[j
].u
), v
= find(V
[j
].v
);
if(u
!= v
) s
[v
] = u
;
}
for(int j
= 2; j
<= j
; j
++)
if(find(g
[j
].id
) != find(g
[1].id
)){
double tem
= (double)(g
[j
].w
+ g
[1].w
) / (ans
- V
[i
].len
);
maxn
= max(maxn
, tem
);
break;
}
}
printf("%.2lf\n", maxn
);
}
int main(){
scanf("%d", &T
);
while(T
--){
t
= ans
= 0;
scanf("%d", &n
);
for(int i
= 1; i
<= n
; i
++){ scanf("%d%d%d", &g
[i
].x
, &g
[i
].y
, &g
[i
].w
); g
[i
].id
= i
;}
for(int i
= 1; i
<= n
; i
++)
for(int j
= i
+ 1; j
<= n
; j
++)
e
[t
].u
= i
, e
[t
].v
= j
, e
[t
].len
= len(i
, j
), e
[t
++].w
= g
[i
].w
+ g
[j
].w
;
kruskal();
solve();
}
return 0;
}
