随笔-19  评论-1  文章-0  trackbacks-0

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

Kruscal最小生成树 注意对double类型的快排可不要写错了
#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->> bb->? 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>1000break;
            
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 孟起 阅读(557) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理