首页 > 代码库 > zoj1203最小生成树

zoj1203最小生成树

#include<stdio.h>#include<iostream>#include<string.h>#include<queue>#include<stack>#include<list>#include<stdlib.h>#include<algorithm>#include<vector>#include<map>#include<set>#include<math.h>using namespace std;int father[10000];int getfather(int x){    if(x!=father[x])        father[x]=getfather(father[x]);    return father[x];}struct Node{    int a;int b;double dist;}node[111111];double dist(double x,double y,double x1,double y1){    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));}bool cmp(const Node & a,const Node &b){    if(a.dist<b.dist) return true;    return false;}int main(){    int n;    double x[1000],y[1000];    int Icase=0;    while(cin>>n,++Icase&&n){        for(int i=1;i<=n;i++)            father[i]=i;        for(int i=1;i<=n;i++){            cin>>x[i]>>y[i];        }        int ans=0;        for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++){            double dis=dist(x[i],y[i],x[j],y[j]);          //  cout<<x[i]<<" "<<y[i]<< " "<<x[j]<< " "<<y[j]<<" "<<dis<<endl;system("pause");            node[ans].a=i;node[ans].b=j;node[ans++].dist=dis;        }        sort(node,node+ans,cmp);      //  for(int i=0;i<ans;i++)         //   cout<<node[i].a<<" "<<node[i].b<<" "<<node[i].dist<<endl;        double sum=0;        for(int i=0;i<ans;i++){            int a=node[i].a;int b=node[i].b;            int fa=getfather(a);int fb=getfather(b);            if(fa!=fb){                father[fa]=fb; sum+=node[i].dist;            }        }        if(Icase>1) cout<<endl;        printf("Case #%d:\n",Icase);        cout<<"The minimal distance is: ";        printf("%.2lf",sum);        cout<<endl;    }    return 0;}