http://acm.hdu.edu.cn/showproblem.php?pid=1875
Kruscal最小生成樹 注意對(duì)double類型的快排可不要寫錯(cuò)了
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct road{
int x,y;
double v;
}r[5002];
struct point{
int a,b;
}p[102];
int cmp(const void *a,const void *b)
{
struct road *aa=(struct road *)a;
struct road *bb=(struct road *)b;
return aa->v > bb->v ? 1:-1;
}
int bin[102];
int find(int x)
{
int r=x;
while(bin[r]!=r)
r=bin[r];
int y=x;
while(bin[y]!=y)
{
y=bin[y];
bin[y]=r;
}
return r;
}
int main()
{
int t,n,i,j,num,cnt;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&p[i].a,&p[i].b);
num=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
r[num].x=i, r[num].y=j;
r[num].v=sqrt(1.0*(p[i].a-p[j].a)*(p[i].a-p[j].a)+(p[i].b-p[j].b)*(p[i].b-p[j].b));
num++;
}
for(i=0;i<n;i++)
bin[i]=i;
qsort(r,num,sizeof(r[0]),cmp);
i=0; ans=0; cnt=0;
while(r[i].v<10)
i++;
for(;i<num && cnt<n-1;i++)
{
if(r[i].v>1000) break;
int fx=find(r[i].x), fy=find(r[i].y);
if(fx!=fy)
{
bin[fx]=fy;
cnt++;
ans+=r[i].v;
}
}
if(cnt==n-1)
printf("%.1lf\n",ans*100);
else
printf("oh!\n");
}
return 0;
}
posted on 2010-10-06 10:26
孟起 閱讀(609)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論