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

因此要对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 ;
}

最新文章

  1. 《Entity Framework 6 Recipes》中文翻译系列 (24) ------ 第五章 加载实体和导航属性之查询内存对象
  2. org.hibernate.NonUniqueObjectException: a different object with the same identifier value was alread---------程序报错
  3. ssh免密登录
  4. Leetcode 234 Palindrome Linked List 链表
  5. scan design flow(二)
  6. C#连接SQL Server数据库进行简单操作
  7. Google C++ 编程规范总结
  8. css3学习笔记之2D转换
  9. iOS 性能优化:Instruments
  10. 利用 C++ 单向链表实现队列
  11. jquery全选框的实现
  12. LeetCode 327. Count of Range Sum
  13. 关于No qualifying bean of type [XXX.XXX] found for dependency 的一次记录
  14. Codeforces Round #321 (Div. 2) E - Kefa and Watch
  15. ps教程
  16. codeforces 982 c
  17. day11有参装饰器,无参装饰器
  18. delphi http 403 获取不到服务器返回的错误消息 用浏览器打开url可以返回
  19. QMetaEnum利用Qt元数据实现枚举(enum)类型值及字符串转换
  20. 出现The folder is already a source folder

热门文章

  1. xml、xhtml、html、dhtml的区别
  2. PHP中的ob_start() 的使用
  3. 20151211jquery ajax进阶代码备份
  4. angularjs + springmvc 上传和下载
  5. cognos 10.2.2 Framework manager使用&rdquo;数据源&rdquo;新建查询主题
  6. Object-C在Nil上调用方法
  7. ASP.NET中的验证控件
  8. hibernate中fetch lazy
  9. react组件什么周期记录,转的
  10. CentOS 配置Apache+Mysql+PHP (yum)与卸载