暢通工程再續 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10216 Accepted Submission(s): 3113 Problem Description 相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過劃小船來實現。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實現百島湖的全暢通！經過考察小組RPRush對百島湖的情況充分了解後，決定在符合條件的小島間建上橋，所謂符合條件，就是2個小島之間的距離不能小於10米，也不能大於1000米。當然，為了節省資金，只要求實現任意2個小島之間有路通即可。其中橋的價格為 100元/米。 Input 輸入包括多組數據。輸入首先包括一個整數T(T <= 200)，代表有T組數據。 每組數據首先是一個整數C(C <= 100),代表小島的個數，接下來是C組坐標，代表每個小島的坐標，這些坐標都是 0 <= x, y <= 1000的整數。 Output 每組輸入數據輸出一行，代表建橋的最小花費，結果保留一位小數。如果無法實現工程以達到全部暢通，輸出”oh!”. Sample Input 2 2 10 10 20 20 3 1 1 2 2 1000 1000 Sample Output 1414.2 oh! #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; int father[111]; double s; struct ssss { double a,b; }ss[111]; struct road { int a,b; double x; }rr[5000]; int Find(int a) { return a==father[a]?a:father[a]=Find(father[a]); } void Union(int i) { int a=Find(rr[i].a),b=Find(rr[i].b); if(a!=b&&rr[i].x<=1000&&rr[i].x>=10) //非同族且距離不大於1000不小於10 father[a]=b,s+=rr[i].x; } bool cmp(const road &a,const road &b) { return a.x<b.x; } int main (void) { int t,n,m,i,j,k,l; cin>>t; while(t--&&cin>>n) { m=n*(n-1)/2; for(i=0;i<1111;i++)father[i]=i; for(i=1;i<=n;i++) cin>>ss[i].a>>ss[i].b; //ss數組用來記錄每個島的坐標 for(i=1,l=0;i<=n;i++) for(j=i+1;j<=n;j++) { rr[l].a=i;rr[l].b=j; //rr用a和b記錄兩個島 double x=ss[i].a-ss[j].a,y=ss[i].b-ss[j].b; rr[l].x=sqrt(x*x+y*y); //x用來記錄兩島之間的距離****關鍵---轉化問題 l++; } sort(rr,rr+l,cmp); //按照距離排序 for(i=s=0;i<l;i++) Union(i); for(i=1,k=0;i<=n&&k<2;i++) if(father[i]==i)k++; //用k標記是否連通了 if(k>=2)cout<<"oh!"<<endl; else printf("%.1f\n",s*100); } return 0; }
