步骤是先求最小生成树,然后选两个不同的点,遍历所有的这样的点,选出两点人口比较大,而且连通两点的边的最大边比较大的情况。

因此要对i,j点连接起来的边进行遍历。

 #include<stdio.h>
#include<string.h>
#include<math.h>
#define N 1010
#define max(a,b) ((a)>(b)?(a):(b))
#define INF 999999999 double map[N][N],lowcost[N],cost[N][N];
int vis[N];/*-1表示该点已经加入,非0表示i和vis[i]的值表示的点构成一条短边*/
int n;
typedef struct
{
double x,y,w;
} Point;
Point point[N]; double dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} void input(void)
{
int i,j;
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].w);
for(i=; i<n-; i++)
for(j=i+; j<n; j++)
map[i][j]=map[j][i]=dis(point[i],point[j]);
} double prim(void)
{
memset(cost,,sizeof(cost));
memset(vis,,sizeof(vis));
double ans=;
int e=,i,j;/*e=0表示首先将点0加入集合U*/
vis[]=-;/*e用来记录新加入的顶点*/
for(i=; i<n; i++)
lowcost[i]=1.0*INF;
for(i=; i<n-; i++)
{
double micost=1.0*INF;
int miedge=-;
for(j=; j<n; j++)
if(vis[j]!=-)
{
double temp=map[e][j];
if(temp<lowcost[j])
{
lowcost[j]=temp;
vis[j]=e;
}
if(lowcost[j]<micost)
micost=lowcost[miedge=j];
}
ans+=micost;
cost[miedge][vis[miedge]]=cost[vis[miedge]][miedge]=map[vis[miedge]][miedge];
for(j=; j<n; j++)
if(vis[j]==-)
cost[j][miedge]=cost[miedge][j]=max(cost[miedge][vis[miedge]],cost[j][vis[miedge]]);
vis[e=miedge]=-;
}
return ans;
} void solve(void)
{
int i,j;
double mst=prim();
/* printf("%f\n",mst);*/
double ans=-;
for(i=; i<n-; i++)
for(j=i+; j<n; j++)
{
double t=(point[i].w+point[j].w)/(mst-cost[i][j]);
ans=max(ans,t);
}
printf("%.2f\n",ans);
} int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
input();
solve();
}
return ;
}
05-07 15:14