用算法解决“百岛湖”的交通问题

问题描述：

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组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!  
Author 8600  
Source 2008浙大研究生复试热身赛（2）——全真模拟  
Recommend lcy   |   We have carefully selected several similar problems for you:  1879 1301 1162 1325 3371 

#include#include#include#includeusing namespace std;
int fa[105],n;//n是小岛数 
struct node//存贮第一次输入的坐标，一定要是浮点型的
{
    double x,y;
}c[105];
struct node1//存贮两个小岛的编号和小岛的距离
{
    int a,b;
    double l;
}eg[10005];
bool cmp(node1 x,node1 y)//比较函数
{
    return x.l<y.l;
}
int find(int x)//查找根并且缩短路径
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void init()//初始化
{
    for(int i=0;i<n;i++)
    fa[i]=i;
}
int main()
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d",&n);
        init();
        memset(&c,0,sizeof(&c));
        memset(&eg,0,sizeof(&eg));
        for(int i=0;i<n;i++)
        scanf("%lf %lf",&c[i].x,&c[i].y);
        int k=0;
        for(int i=0;i<n;i++)
        for(int j=i+1;j=10&&temp<=1000)//如果距离大于等于10小于等于1000
            {
                eg[k].a=i,eg[k].b=j,eg[k].l=temp;
                k++;        
            }
        }
        sort(eg,eg+k,cmp);//根据距离排序
        double sum=0;//计算最小生成树的和
        for(int i=0;i<k;i++)
        {
            int x=find(eg[i].a);
            int y=find(eg[i].b);
            if(x!=y)
            fa[x]=y,sum+=eg[i].l;
        }
        int count=0;
        for(int i=0;i<n;i++)//判断树根个数
        if(fa[i]==i)
        count++;
        if(count!=1)
        printf("oh!n");
        else
        printf("%.1lfn",sum*100);
    }
    return 0;
}