HDU - 1875 - 畅通工程再续

港控/mmm° 2022-06-10 00:39 128阅读 0赞

--------------------

题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1875][http_acm.hdu.edu.cn_showproblem.php_pid_1875]

## 题目描述 ##

### Description ###

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组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!

## 解题思路 ##

因为给的是坐标，首先把各个点之间的距离算出来，然后存入二维数组，下标为起点终点，在给数组传入数据的时候，把不符合规定的定义为inf。然后就是最小生成树的内容了。  
[最小生成树详解][Link 1]

## AC代码 ##

#include<iostream>
    #include<cstring>
    #include<cmath>
    #define inf 0x3f3f3f3f
    #define maxn 110
    using namespace std;
    
    int n;
    bool use[maxn];
    double dis[maxn];
    double map[maxn][maxn];
    
    struct node {
        int x, y;
    }cnt[maxn];
    
    double count(int a, int b, int c, int d) {
        double ans = (double)((a-c)*(a-c) + (b-d)*(b-d));
        if(100 <= ans && ans <= 1000000) return sqrt(ans);
        else return inf;
    }
    
    double prime() {
        double ans = 0.0;
        for(int i = 1; i <= n; i++) {
            dis[i] = map[1][i]; 
        } 
        memset(use, false, sizeof(use));
        use[1] = true;
        for(int i = 1; i <= n; i++) {
            double minn = inf;
            int u;
            for(int j = 1; j <= n; j++) {
                if(!use[j] && dis[j] < minn) {
                    minn = dis[u = j];
                }
            }
            if(minn == inf) break;
            ans += minn;
            use[u] = true;
            for(int j = 1; j <= n; j++) {
                if(!use[j] && dis[j] > map[u][j])
                    dis[j] = map[u][j];
            }
        }
        return ans;
    }
    
    int main () {
        int t;
        cin >> t;
        while(t--) {
            cin >> n;
            for(int i = 1; i <= n; i++) {
                cin >> cnt[i].x >> cnt[i].y;
            }
            for(int i = 1; i <= n; i++) {
                for(int j = i; j <= n; j++) {
                    if(i == j) map[i][j] = 0.0;
                    else map[i][j] = map[j][i] = count(cnt[i].x, cnt[i].y, cnt[j].x, cnt[j].y);
                }
            }
            double num = prime();
            if(num == 0.0) printf("oh!\n");
            else printf("%.1lf\n", num*100);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1875]: http://acm.hdu.edu.cn/showproblem.php?pid=1875
[Link 1]: http://blog.csdn.net/xiao_bai_9527/article/details/76730366