暢通工程再續(xù)

Problem Description
相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當(dāng)他們想去其他的小島時都要通過劃小船來實現(xiàn)。現(xiàn)在政府決定大力發(fā)展百島湖，發(fā)展首先要解決的問題當(dāng)然是交通問題，政府決定實現(xiàn)百島湖的全暢通！經(jīng)過考察小組RPRush對百島湖的情況充分了解后，決定在符合條件的小島間建上橋，所謂符合條件，就是2個小島之間的距離不能小于10米，也不能大于1000米。當(dāng)然，為了節(jié)省資金，只要求實現(xiàn)任意2個小島之間有路通即可。其中橋的價格為 100元/米。
?

Input
輸入包括多組數(shù)據(jù)。輸入首先包括一個整數(shù)T(T <= 200)，代表有T組數(shù)據(jù)。
每組數(shù)據(jù)首先是一個整數(shù)C(C <= 100),代表小島的個數(shù)，接下來是C組坐標，代表每個小島的坐標，這些坐標都是 0 <= x, y <= 1000的整數(shù)。
?

Output
每組輸入數(shù)據(jù)輸出一行，代表建橋的最小花費，結(jié)果保留一位小數(shù)。如果無法實現(xiàn)工程以達到全部暢通，輸出”oh!”.
?

Sample Input
2 2 10 10 20 20 3 1 1 2 2 1000 1000
?

裸題，思路在之前的博客里！

#include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> //---------------------------------Sexy operation--------------------------//#define cini(n) scanf("%d",&n) #define dis(a,b,c,d) ((double)sqrt((a-c)*(a-c)+(b-d)*(b-d))) using namespace std; //___________________________Dividing Line__________________________________/# #define N 105 int fa[N],a[N],b[N],tot; struct Node {int x,y;double len;bool operator< (const Node w)const{return len<w.len;} }dis[N*N]; int find(int x) {if(fa[x]==x)return x;else return fa[x]=find(fa[x]); } int main() {int T;cini(T);while (T--){int n,tot=0,cnt=0;double ans=0;cini(n);for(int i=1; i<=n; i++)cini(a[i]),cini(b[i]);for(int i=1; i<=n; i++)for(int j=i+1; j<=n; j++){double d=dis(a[i],b[i],a[j],b[j]);//cout<<d<<endl;if(d<=1000&d>=10){dis[++tot].x=i;dis[tot].y=j;dis[tot].len=d;}}// cout<<tot<<endl;sort(dis+1,dis+1+tot);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=tot;i++){int xx=find(dis[i].x),yy=find(dis[i].y);if(xx!=yy){cnt++;ans+=dis[i].len*100;fa[yy]=xx;if(cnt==n-1) break;}}if(cnt==n-1) printf("%.1f\n",ans);else puts("oh!");} }

?

?

總結(jié)

以上是生活随笔為你收集整理的HDU-1857 畅通工程再续的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。