注意精度问题,不要用强转。
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <iostream> #include <cmath> #define N 1010 #define INF 0x3f3f3f3f using namespace std; int n; double x[N],y[N]; double dis[N][N]; double d[N]; int vis[N]; bool mp[N][N]; double ans; struct Edge{ int v,next; }edge[N*2]; int head[N],cnt; double dp[N][N]; void init(){ memset(head,-1,sizeof(head)); cnt=0; } void addedge(int u,int v){ edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].next=head[v]; head[v]=cnt++; } double ren[N]; void prim(){ for(int i=0;i<n;i++){ vis[i]=0; d[i]=dis[0][i]; } vis[0]=-1; ans=0; memset(mp,0,sizeof(mp)); for(int i=1;i<n;i++){ double Min=(double)INF; int node=-1; for(int j=0;j<n;j++){ if(vis[j]!=-1 && d[j]<Min){ node=j; Min=d[j]; } } ans+=Min; mp[vis[node]][node]=mp[node][vis[node]]=1; addedge(vis[node],node); vis[node]=-1; for(int j=0;j<n;j++){ if(vis[j]!=-1 && d[j]>dis[node][j]){ vis[j]=node; d[j]=dis[node][j]; } } } } struct node{ double maxdis; int to, fa; node(double a=0,int b=0, int c=0):maxdis(a),to(b),fa(c){} }; void BFS(int x){ queue<node>q; q.push(node(0,x,-1)); while(!q.empty()){ node u = q.front(); q.pop(); for(int i = head[u.to]; ~i; i = edge[i].next){ int v = edge[i].v; if(v == u.fa)continue; double nowmax = max(dis[u.to][v], u.maxdis); dp[x][v] = dp[v][x] = max(dp[x][v], nowmax); q.push(node(nowmax, v, u.to)); } } } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf %lf %lf",&x[i],&y[i],&ren[i]); for(int i=0;i<n;i++) for(int j=i;j<n;j++) dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); init(); prim(); for(int i=0;i<n;i++) for(int j=i;j<n;j++) dp[i][j]=dp[j][i]=0; for(int j=0;j<n;j++) BFS(j); double ANS=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(mp[i][j]) ANS=max(ANS,(ren[i]+ren[j])/(ans-dis[i][j])); else ANS=max(ANS,(ren[i]+ren[j])/(ans-dp[i][j])); printf("%.2lf\n",ANS); } return 0; } /* 99 4 1 1 20 1 2 30 200 2 80 200 1 100 3 1 1 20 1 2 30 2 2 40 */