题目
戳这里
题解
从今天起我要改邪归正，好好刷题准备联赛！
这是一道经典的最小生成树题目。 枚举每一条边作为道士要修的路，求出包含这条边的最小生成树。
先求出原图的最小生成树。 如果要删的边在最小生成树上，那仍是原来那个最小生成树。 如果不在，便要把这条边加进去。类似次小生成树，删除原最小生成树中这两点间唯一路径上边权最大的边，并把这条边加进去。
我们要预处理最小生成树上两点间路径上边权最大的边，设它的边权为 \(f[u][v]\) 在求最小生成树的同时 借助父节点更新某一节点到已有生成树中其它节点的 \(f\) 值，复杂度 \(O(n^2)\)
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N = 1005;
typedef double db;
typedef pair<double,int> P;
int w[N],vis[N];
db mp[N][N],a[N],b[N];
int n;
priority_queue< P, vector<P>, greater<P> > que;
db d[N],f[N][N],S;
int fa[N];
void prim(){
d[1]=0; vis[1]=1;
for(int i=2;i<=n;i++)
d[i]=mp[1][i],fa[i]=1,que.push(P(d[i],i));
while(!que.empty()){
int u=que.top().second;
que.pop();
if(vis[u]) continue;
for(int i=1;i<=n;i++)
if(vis[i]) {
if(i==fa[u]) f[i][u]=f[u][i]=mp[u][i];
else f[i][u]=f[u][i]=max(mp[u][fa[u]],f[fa[u]][i]);
}
vis[u]=1; d[u]=0;
S+=mp[u][fa[u]];
for(int v=1;v<=n;v++){
if(v==u) continue;
if(d[v]>mp[u][v])
fa[v]=u,d[v]=mp[u][v],que.push(P(d[v],v));
}
}
for(int i=1;i<=n;i++) vis[i]=0;
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf%d",&a[i],&b[i],&w[i]);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
mp[i][j]=mp[j][i]=sqrt((b[i]-b[j])*(b[i]-b[j])+(a[i]-a[j])*(a[i]-a[j]));
S=0;
prim();
db ans=0.0;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
ans=max(ans,(w[i]*1.0+w[j]*1.0)/(S-f[i][j]));
printf("%.2lf\n",ans);
}
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/9733349.html
