hdu1875

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

2

2

10 10

20 20

3

1 1

2 2

1000 1000

给定坐标

 //最小生成树
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
const int N=;
int father[N];
int n,m,g;
struct stu{
int n;
int x;
int y;
}q[N];
struct ln{
int u;
int v;
double w;
}p[N]; int cmp(const void *a,const void *b)
{
return (*(struct ln*)a).w >(*(struct ln*)b).w ?:-;
} int find(int x)
{
if(father[x]!=x)
father[x]=find(father[x]);
return father[x];
}
int make(int a,int b)
{
int h=;
int f1=find(a);
int f2=find(b);
if(f1<f2)
{
father[f2]=f1;
h=;
}
else if(f1>f2)
{
father[f1]=f2;
h=;
}
return h;
} double kruskal()
{
double s=;
int k=;
for(int i=;i<m;i++)
{
if(make(p[i].u,p[i].v))
{
if(p[i].w==)
g=;
s+=p[i].w;
k++;
}
if(k==n-)
return s*;
}
return s*;
} void zuhe()//道路分析
{
int k=;
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++,k++)
{
p[k].u=i;
p[k].v=j;
p[k].w=sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
if(p[k].w< || p[k].w>)
{
p[k].w=;
}
//printf("%d %d %lf\n",p[k].u,p[k].v,p[k].w);
}
}
} int main()
{
//freopen("in.txt","r",stdin);
int t;
double s;
scanf("%d",&t);
while(t--)
{
g=;
scanf("%d",&n);
m=n*(n-)/;
for(int i=;i<=n;i++)
{
father[i]=i;
}
for(int i=;i<=n;i++)
{
q[i].n=i;
scanf("%d%d",&q[i].x,&q[i].y);
}
zuhe();
qsort(p,m,sizeof(struct ln),cmp);
s=kruskal();
if(g==)
{
printf("oh!\n");
continue;
}
printf("%.1lf\n",s);
}
return ;
}
上一篇:iOS Document Interaction(预览和打开文档) 编程指南


下一篇:setOnClickListener报空指针异常