畅通project再续

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 18411 Accepted Submission(s): 5769

Problem Description

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其它的小岛时都要通过划小船来实现。

如今政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！

经过考察小组RPRush对百岛湖的情况充分了解后。决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米。也不能大于1000米。当然，为了节省资金，仅仅要求实现随意2个小岛之间有路通就可以。

当中桥的价格为 100元/米。

Input

输入包含多组数据。

输入首先包含一个整数T(T <= 200)，代表有T组数据。

每组数据首先是一个整数C(C <= 100),代表小岛的个数。接下来是C组坐标，代表每一个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output

每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。假设无法实现project以达到所有畅通，输出”oh!”.

Sample Input

Sample Output

1414.2

oh!

Author

8600

Source

2008浙大研究生复试热身赛（2）——全真模拟

Recommend

lcy | We have carefully selected several similar problems for you: 1233

pid=1232" style="color:rgb(26,92,200); text-decoration:none">1232 1863 1874 1102

最小生成树问题。两种算法prim和kruskal。在这里我用的另外一种算法

第一次RE了。。

原来数组太小了。。。CNN!!

分别计算n各小岛各个的距离（小于10大于1000的不要），而且存到结构体eg里面。sort依据距离从小到大排序，然后就用kruskal算法。

最后推断树根是否仅仅有一个。

还是看代码来的实在，有简单凝视

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

int fa[105],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<n;j++)

        {

            double temp=sqrt(pow(c[i].x-c[j].x,2)+pow(c[i].y-c[j].y,2));

            if(temp>=10&&temp<=1000)//假设距离大于等于10小于等于1000

            {

                eg[k].a=i,eg[k].b=j,eg[k].l=temp;

                k++;

            }

        }

        sort(eg,eg+k,cmp);//依据距离排序<span style="white-space:pre">	</span>

        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("%.1lf\n",sum*100);

    }

    return 0;

}

巴特西

hdu 1875 畅通project再续（kruskal算法计算最小生成树）

畅通project再续

最新文章

热门文章