解析：最小生成树；Kruskal 算法：并查集实现。
1、首先找出符合要求的边；
2、对找出的边排序；
3、并查集找出n-1条边，无法修通n-1条路则无法实现要求。
#include<iostream> #include<cmath>#include<algorithm>using namespace std;struct Point{int x,y;} point[102];struct Edge{int a,b;double v;bool operator<(const Edge a){return v<a.v;}} edge[5002];int p[102];double Distance(Point a,Point b){return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0));}bool Init(int n)//一开始指向自己{for(int i=0;i<=n;i++)p[i]=i;return true;}int Find(int x)//找到根节点{int r,i,j;r=x;while(r!=p[r]) r=p[r];//路径压缩准备,找到根节点i=x;while(i!=p[i]){j=p[i];p[i]=r;i=j;}return i;//返回根节点}bool Merge(int x,int y)//返回是否需要合并{int tx,ty;tx=Find(x);ty=Find(y);if(tx==ty) return false;p[tx]=ty;return true;}int main() { int T,C,i,j,k,cnt;int tx,ty;double dis,sum;scanf("%d",&T);while(T–){scanf("%d",&C);k=0;for(i=1;i<=C;i++){scanf("%d%d",&point[i].x,&point[i].y);for(j=1;j<i;j++){dis=Distance(point[i],point[j]);if(dis>=10 && dis<=1000)//计算满足要求的边{edge[k].a=i;edge[k].b=j;edge[k++].v=dis;}}}Init(C);sort(edge,edge+k);cnt=C-1;sum=0;for(i=0;i<k;i++){tx=Find(edge[i].a);ty=Find(edge[i].b);if(tx!=ty)//增加一条路，，知道增加完C-1条{Merge(tx,ty);sum+=edge[i].v;cnt–;if(cnt==0) break;}}if(!cnt)//cnt不为0就不能修C-1条路printf("%.1lf\n",sum*100);else puts("oh!");}return 0; }
生命中,每一种苦难的背后都有一片晴朗的天空
