HDU 1875(最小生成树)
2024-08-30 05:08:36
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
typedef struct
{
int a,b;
double v;
}node;
typedef struct
{
int a,b;
}P;
const int maxn=;
double ans;
int father[maxn];
node graph[maxn*(maxn-)/];
P p[maxn];
int Find(int x)
{
if(father[x]==x)
return x;
else
{
father[x]=Find(father[x]);
return father[x];
}
}
void Union(int x,int y,double v)
{
if(Find(x)!=Find(y))
{
ans+=v*;
father[Find(x)]=Find(y);
}
return;
}
bool cmp(node x,node y)
{
if(x.v<y.v)
return true;
else
return false;
}
int main()
{
double V;
int n;
scanf("%d",&n);
while(n--)
{
ans=;
for(int i=;i<maxn;i++)
father[i]=i;
int m,k;
k=;
scanf("%d",&m);
for(int i=;i<m;i++)
{
scanf("%d%d",&p[i].a,&p[i].b);
}
for(int i=;i<m-;i++)
{
for(int j=i+;j<m;j++)
{
V=sqrt(pow((p[i].a-p[j].a),2.0)+pow((p[i].b-p[j].b),2.0));
if(V<=&&V>=)
{
graph[k].a=i;
graph[k].b=j;
graph[k].v=V;
k++;
}
}
}
sort(graph,graph+k,cmp);
for(int i=;i<k;i++)
Union(graph[i].a,graph[i].b,graph[i].v);
int xx=Find();
int flag;
flag=;
for(int i=;i<m;i++)
{
if(Find(i)!=xx)
{
flag=;
break;
}
}
if(flag==)
printf("oh!\n");
else
printf("%.1lf\n",ans);
}
return ;
}
最新文章
- CSS currentColor 变量的使用
- 最新WingIDE注册破解方法 【转】
- effetive C++ 02 尽量以const,enum,inline替换#define
- java 22 - 19 多线程之生产者和消费者的代码优化
- 两款CSS3样式可视化在线生成工具
- Redis源码研究--双向链表
- 体验Azure的 Automation “自动化” 服务预览版
- java多线程总结三:sleep()、join()、interrupt()示例
- SharePoint 2010 WSP包部署过程中究竟发生什么?
- 【HtmlParser】HtmlParser使用
- hdu 4640 Island and study-sister
- HTML:scrollLeft,scrollWidth,clientWidth,offsetWidth到底指的哪到哪的距离之完全详解
- javascript 动态推断html元素
- Tier和Layer
- iOS开发中怎么样使用激光推送
- Leetcode 136 Single Number 仅出现一次的数字
- pygame-KidsCanCode系列jumpy-part2-加速度与摩擦力
- 10个非常炫酷的jQuery相册动画赏析
- 更简单的调试Release版本Optimize code的.NET程序集
- 使用pool的多进程,不执行的问题