hdu 1875 畅通工程再续

#include <iostream>#include <algorithm>#include <iomanip>#include <cmath>using namespace std;int n,p[105]; struct point{    double x,y,d; }e[15005],zb[105];int cmp(point a1,point b1){    return a1.d<b1.d;}void init(){    for(int i=1;i<=n;i++)     p[i]=i;}int find(int x){    if(x==p[x]) return x;    else return p[x]=find(p[x]);}void jie(int x,int y){    int ta=find(x),tb=find(y);    if(ta!=tb) p[ta]=tb;}double clus(int m){    int x,y,i,c; double ans;    init();    for(ans=c=i=0;i<m;i++)    {        x=e[i].x;y=e[i].y;        if(find(x)!=find(y))        {   ans+=e[i].d;             c++;            jie(x,y);        }        if(c==n-1) return ans;    }    return -1;}int main(void){   int t,i,j,k;double d;   cin>>t;   while(t--)   {     cin>>n;     for(i=1;i<=n;i++)      cin>>zb[i].x>>zb[i].y;      if(n==1) cout<<0<<endl;      for(k=0,i=1;i<=n;i++)      for(j=i+1;j<=n;j++)       { d=sqrt((zb[i].x-zb[j].x)*(zb[i].x-zb[j].x)+(zb[i].y-zb[j].y)*(zb[i].y-zb[j].y));         if(d<10||d>1000)  continue;        e[k].x=i; e[k].y=j; e[k++].d=d;       }       if(k<n-1) {cout<<"oh!"<<endl;continue;}       sort(e,e+k,cmp);   d=clus(k);       if(d==-1) cout<<"oh!"<<endl;       else cout<<fixed<<setprecision(1)<<d*100<<endl;   }  }