题目链接
题目大意：
秦始皇要在n个城市之间修筑一条道路使得任意两个城市均可连通。有个道士可以用法力帮忙修一条路。秦始皇希望其他的道路总长B最短且用法术连接的两个城市的人口之和A尽量大，因此下令寻找一个A / B的最大方案。
solution：这道题换个问法就是：在o(1),时间内求出最小生成树删去一条边后的权值。
我们可以先求出最小生成树的权值 minlen， 再o(n^2)求出节点间最小瓶颈路mx[u][v]，那么原题中 B=minlen-mx[u][v], 再枚举u，v算出 A 就可以求出答案max（A/B ）了。
如何求每对节点间最小瓶颈路 ？？
先介绍几个概念
1.最小瓶颈生成树：给出加权无向图，求一颗生成树使得最大边权值尽量小。
怎么求？
我们先把边排序，然后从小到大，如果该边的两个节点没有被连通，那么就把它们加入生成树中。这个过程。。。就是Kruskal呀。 ====> 最小生成树就是最小瓶颈生成树
2.最小瓶颈路：给出加权无向图的两个节点u，v， 求出u到v的路径中最长边的最小值。
怎么搞？？
先求出最小瓶颈生成树，在求u，v在最小瓶颈生成树上的路径的最长边。
3.每对节点的最小瓶颈路： 就是每对节点( u, v )之间的最小瓶颈路
显然，我们可以先求出最小生成树，再用dfs搞。
令： x为所有访问过的节点， u为当前节点， fa为当前节点的父亲节点
则有 mx[u][x]=mx[x][u]=max(mx[x][fa],w[x][fa])
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =
1e3 +
5;
struct P{
int x, y;
int num;
}p[N];
struct E{
int u, v;
double dis;
}e[N*N];
struct Edge{
int u, v;
double w;
Edge(
int u,
int v,
double w):u(u),v(v),w(w){}
};
vector<Edge> edges;
vector<int> G[N];
int n, m;
void addeage(
int u,
int v,
double w){
edges.push_back(Edge(u,v,w));
int k=edges.size();
G[u].push_back(k-
1);
}
int pa[N];
int find(
int x){
int r=x;
while( r!=pa[r] ) r=pa[r];
int i=x, j;
while( i!=pa[i] ){
j=pa[i];
pa[i]=r;
i=j;
}
return r;
}
bool merge(
int x,
int y){
x=find(x), y=find(y);
if( x==y )
return false;
pa[x]=y;
return true;
}
double minlen;
double mx[N][N];
vector<int> nodes;
bool cmp(E a, E b){
return a.dis<b.dis;
}
void Kruskal(){
int em=
0;
for (
int i=
1; i<=n; i++ )
for (
int j=i+
1; j<=n; j++ ){
e[em].u=i, e[em].v=j;
e[em++].dis=
sqrt( (
double)(p[i].x-p[j].x)*(p[i].x-p[j].x) + (
double) (p[i].y-p[j].y)*(p[i].y-p[j].y) );
}
sort(e,e+em,cmp);
int num=
0;
minlen=
0;
for (
int i=
1; i<=n; i++ ) pa[i]=i;
for (
int i=
0; i<em; i++ )
if( merge(e[i].u,e[i].v) && num<n-
1 ){
num++;
minlen+=e[i].dis;
addeage(e[i].u,e[i].v,e[i].dis);
addeage(e[i].v,e[i].u,e[i]. dis);
}
}
void dfs(
int u,
int fa,
double dis){
for (
int i=
0; i<nodes.size(); i++ ){
int id=nodes[i];
mx[u][id]=mx[id][u]=max(mx[fa][id],dis);
}
nodes.push_back(u);
for (
int i=
0; i<G[u].size(); i++ ){
Edge ee=edges[G[u][i]];
if( ee.v==fa )
continue;
dfs(ee.v,u,ee.w);
}
}
int main(){
int T;
scanf(
"%d", &T );
while( T-- ){
scanf(
"%d", &n );
edges.clear();
for (
int i=
1; i<=n; i++ ) G[i].clear();
nodes.clear();
memset(mx,
0,
sizeof(mx));
for (
int i=
1; i<=n; i++ ){
int x1, x2, x3;
scanf(
"%d%d%d", &p[i].x, &p[i].y, &p[i].num );
}
Kruskal();
dfs(
1,
0,
0);
double ret=-
1;
for (
int i=
1; i<=n; i++ )
for (
int j=i+
1; j<=n; j++ ){
ret=max(ret,(
double)(p[i].num+p[j].num)/(minlen-mx[i][j]));
}
printf(
"%.2lf\n",ret);
}
}
