栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2560 Freckles

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2560 Freckles

#include<cstdio>#include<algorithm>#include<cmath> #include<cstring>#include<iostream>double x[11000],y[11000];int fa[10010];double sum=0;using namespace std;struct side{int u;int v;double d;}s[10010];int tt;int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}inline void unition(int a,int b){fa[get(a)]=get(b);}inline void krr(int ns,int np) {for(int i=1;i<=ns;i++){int pa=get(s[i].u);int pb=get(s[i].v);if(pa!=pb){unition(pa,pb);//cout<<s[i].d<<endl;sum+=s[i].d;tt++;}if(tt==np-1)break;}}bool operator < (side a,side c){if(a.d==c.d){if(a.u==c.u)return a.v<c.v;return a.u<c.u;}return a.d<c.d;}int main(){int np;cin>>np;int tot=0;for(int i=1;i<=10001;i++)fa[i]=i;for(int i=1;i<=np;i++){scanf("%lf%lf",&x[i],&y[i]);for(int j=1;j<i;j++){tot++;s[tot].u=i,s[tot].v=j;s[tot].d=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//cout<<s[i].d<<endl;}}sort(s+1,s+1+tot);krr(tot,np);printf("%.2lfn",sum);return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/378559.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号