程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa 10397 Connect the Campus

UVa 10397 Connect the Campus

編輯:C++入門知識

UVa 10397 Connect the Campus


最小生成樹

Kruskal

#include
#include
#include
#include
using namespace std;

struct A{
    int x,y;
    double z;
}a[500010];
int r[755];
int find_(int x)
{
    while(x!=r[x])
        x=r[x];
    return x;
}

int cmp(A a,A b)
{
    return a.zj){
                    double s=sqrt(  (x[i]-x[j])*(x[i]-x[j])+ (y[i]-y[j])*(y[i]-y[j]) );
                    a[++k].x=i;
                    a[k].y=j;
                    a[k].z=s;
                }
            }
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&c,&b);
            int aa=find_(c);
            int bb=find_(b);
            if(aa!=bb){
                r[aa]=bb;
            }
        }

        sort(a+1,a+1+k,cmp);
        double ans=0;
        for(i=1;i<=k;i++)
        {
            int aa=find_(a[i].x);
            int bb=find_(a[i].y);
            if(aa!=bb){
                r[aa]=bb;
                ans=ans+a[i].z;
            }
        }
        printf("%.2lf\n",ans);


    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved