http://acm.hdu.edu.cn/showproblem.php?pid=1875

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1001
using namespace std;
const int inf=<<; int n;
double g[maxn][maxn];
bool vis[maxn];
double dis[maxn];
double sum;
bool flag=true; struct node
{
int x,y;
}p[maxn]; int sqr(int x)
{
return x*x;
} double dist(int x1,int y1,int x2,int y2)
{
return sqrt(sqr(x1-x2)+sqr(y1-y2));
} void prim()
{
memset(vis,false,sizeof(vis));
for(int i=; i<n; i++) dis[i]=g[][i];
dis[]=;
vis[]=true;
for(int i=; i<n; i++)
{
double m=(double)inf;
int x;
for(int y=; y<n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y];
if(m==inf){flag=false;break;}
sum+=m;
vis[x]=true;
for(int y=; y<n; y++) if(!vis[y]&&dis[y]>g[x][y]) dis[y]=g[x][y]; }
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
if(i==j) g[i][j]=;
else
g[i][j]=g[j][i]=inf;
}
}
for(int i=; i<n; i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
for(int i=; i<n; i++)
{
for(int j=; j<n; j++)
{
if(i!=j){
double d=dist(p[i].x,p[i].y,p[j].x,p[j].y);
if(d>=10.0&&d<=1000.0) g[i][j]=d;
}
}
}
flag=true;
sum=0.0;
prim();
if(!flag) printf("oh!\n");
else
printf("%.1lf\n",(sum*));
}
return ;
}

最新文章

  1. Java中用内存映射处理大文件
  2. Apache Spark技术实战之6 -- spark-submit常见问题及其解决
  3. HDU 1171 Big Event in HDU --暴力+生成函数
  4. Android 利用Service实现下载网络图片至sdk卡
  5. linux strace
  6. oracle schema object
  7. svn 分支
  8. Analyzer使用第二Y轴,以及同一分析图不同量值使用不同的图形样式
  9. Algorithm: quick sort implemented in python 算法导论 快速排序
  10. IOC容器 - Autofac概述
  11. 【其他】MySql常用命令
  12. hdu_1790_The Balance(母函数)
  13. Let the Balloon Rise(水)
  14. linux 查看CPU、内存、磁盘信息命令
  15. 了解原型设计工具pencil project
  16. 移动web图片加载完获取img宽高
  17. jenkins的 git多分支自动构建
  18. 【XSY2715】回文串 树链剖分 回文自动机
  19. 文件内容统计:对任意给定的.txt文件进行内容的字符数、行数、单词数进行统计
  20. What is 软件工程

热门文章

  1. codevs1033 蚯蚓的游戏问题
  2. SPOJ694 -- DISUBSTR 后缀树组求不相同的子串的个数
  3. 将 Web 应用性能提高十倍的10条建议
  4. css(二)
  5. Apache HttpComponents Client 4.0快速入门/升级-2.POST方法访问网页
  6. Android Clipboard(复制/剪贴板)
  7. USB HID Report Descriptor 报告描述符详解
  8. http://msh.baidu.com/UTWpR6wY4722
  9. overcast
  10. 跨域访问-JSONP