（最小生成树）畅通工程再续 -- HDU --1875 畅通工程再续

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1875

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82831#problem/N

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20660 Accepted Submission(s): 6516

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

10 10

20 20

1 1

2 2

1000 1000

Sample Output

1414.2

oh!

代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define N 210
#define INF 0xfffffff
double  G[N][N],dis[N];
int vis[N];

struct node
{
    int x,y;
}p[N];

void Inn()
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        dis[i]=INF;
        for(j=1;j<=N;j++)
        {
            G[i][j]=INF;
        }
    }
    memset(vis,0,sizeof(vis));
}

double prim(int s,int n)
{
    double ans=0;
    int i,j;

    for(i=1;i<=n;i++)
        dis[i]=G[s][i];

    memset(vis, 0, sizeof(vis));
    vis[s]=1;

    for(i=1;i<n;i++)
    {
        int dist=1;
        double Min=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && dis[j]<Min)
            {
                dist=j;
                Min=dis[j];
            }
        }
        vis[dist]=1;
        ans+=Min;
        for(j=1;j<=n;j++)
        {
            if(!vis[j] && dis[j]>G[dist][j])
            {
                dis[j]=G[dist][j];
            }
        }
    }
    return ans;
}
int main()
{
    int T,n,i,j;
    scanf("%d",&T);

    while(T--)
    {
        Inn();

        scanf("%d",&n);
        memset(p,0,sizeof(p));
        for(i=1;i<=n;i++)
            scanf("%d %d",&p[i].x,&p[i].y);

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                double d=sqrt(1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
                if(d>=10 && d<=1000)
                    G[i][j]=G[j][i]=d;
            }
        }
        double aa=prim(1,n);
        if(aa>INF)
            printf("oh!
");
        else
            printf("%.1f
",aa*100);
    }
    return 0;
}

（最小生成树） 畅通工程再续 -- HDU --1875 畅通工程再续

相关推荐

（最小生成树）畅通工程再续 -- HDU --1875 畅通工程再续