因为是全连接图,所以也可以用最小生成树

这道题给边加了一个限制条件,(10<=x<=1000),所以可能不能全连通,需要判断

#include <cstdio>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std; #define sf scanf
#define pf printf
#define debug printf("!\n")
#define blank printf("\n")
#define mem(a,b) memset(a,b,sizeof(a)) const int MaxN = ;
const int INF = <<; int p[MaxN]; int r[MaxN*MaxN],u[MaxN*MaxN],v[MaxN*MaxN];
double w[MaxN*MaxN]; int m,n,vex; struct point
{
int x,y;
}; point pt[]; int find(int x){return p[x]==x?x:p[x]=find(p[x]);} int cmp(const int a,const int b)
{
return w[a]<w[b];
} double kruskal()
{
double ans = ;
int i; for(i = ;i<n;i++) p[i] = i;
for(i = ;i<m;i++) r[i] = i; sort(r,r+m,cmp); for(i = ;i<m;i++)
{
int e = r[i];
int x = find(u[e]);
int y = find(v[e]);
if(x!=y)
{
ans+=w[e];
p[x] = y;
vex++;
}
}
return ans;
} double getD(point p1 ,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
} int main()
{
int i,j,t;
sf("%d",&t);
while(t--)
{
mem(u,);
mem(v,);
mem(w,); m=;
vex = ; sf("%d",&n);
for(i = ;i<n;i++)
{
sf("%d%d",&pt[i].x,&pt[i].y);
} for(i = ;i<n;i++)
{
for(j=i+;j<n;j++)
{
double d = getD(pt[i],pt[j]);
if(d< || d>)
{
continue;
}
u[m] = i;
v[m] = j;
w[m++] = d;
}
} double ans = kruskal(); if(vex<n)
pf("oh!\n");
else
pf("%.1lf\n",ans*);
} return ;
}

最新文章

  1. Oracle并行添加主键的方法
  2. unity生成WP工程后ExtendedSplashImage显示不正确的问题
  3. HTML简明教程(一)
  4. http和socket通信的区别
  5. vs2008编译QT开源项目三国杀(五篇文章)
  6. codeforces.com/contest/325/problem/B
  7. Caused by: com.fasterxml.jackson.core.JsonParseException: Unrecognized token &#39;name&#39;: was expecting (&#39;true&#39;, &#39;false&#39; or &#39;null&#39;)
  8. HTTP2的新特性
  9. Gazebo機器人仿真學習探索筆記(二)基本使用說明
  10. Ubuntu 安装yii2 advanced版 遇到的坑
  11. 第一阶段——CentOS6_Python3.6.1笔记(尚学堂-Python基础快速入门)+ 【补充】麦子-Python程序入门与进阶
  12. mount挂载相关参数详解
  13. asp.net core webapi处理Post请求中的request payload
  14. 【原创】c++拷贝初始化和直接初始化的底层区别
  15. 加密的m3u8、ts文件合并
  16. mongodb创建用户(转发)
  17. Mac OS X 恢复 VMware Fusion 虚拟机中的 vmdk 文件
  18. logbak 配置相关
  19. PAT A1115 Counting Nodes in a BST (30 分)——二叉搜索树,层序遍历或者dfs
  20. AWK学习一例

热门文章

  1. PHP之编写日志文件留后门(免杀)
  2. 工作中遇到的两个问题-正则以及console
  3. [Objective-C语言教程]类型转换(20)
  4. leetcode-139-单词拆分(递归超时,动归解决)
  5. 嵌入式C语言自我修养 05:零长度数组
  6. eclipse如何设置UTF-8
  7. k-近邻算法 python实现
  8. 【APUE】第3章 文件I/O (1)
  9. Spring事务杂谈
  10. (六)Audio子系统之AudioRecord.release