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; } }