N - 畅通工程再续——最小生成树Prim算法+double精度

刺骨的言语ヽ痛彻心扉 2022-06-11 08:08 165阅读 0赞

Think:  
1知识点：最小生成树Prim算法+double精度  
2题意：给定n个坐标，任意两点建边需满足两点距离在\[10, 1000\]范围内，询问能否构成最小生成树，若能则输出最小代价，反之输出“oh!”  
3反思：  
1>题意判断条件需要明确清晰  
2>注意编程细节，变量类型赋值要准确

[vjudge题目链接][vjudge]

以下为Accetped代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const double zero = 0.0001;
    const int N = 114;
    
    struct Node{
        int x, y;
    }node[N];
    
    int vis[N];
    double e[N][N], dis[N];
    
    void Prim(int n);
    
    int main(){
        int T, n, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d %d", &node[i].x, &node[i].y);
            for(i = 1; i <= n; i++){
                e[i][i] = 0;
                for(j = i+1; j <= n; j++){
                    int dx = node[i].x - node[j].x;
                    int dy = node[i].y - node[j].y;
                    int L = dx*dx + dy*dy;
                    if(L >= 100 && L <= 1000000)
                        e[i][j] = e[j][i] = sqrt(L);
                    else
                        e[i][j] = e[j][i] = inf;
                }
            }
            Prim(n);
        }
        return 0;
    }
    void Prim(int n){
        int i, v, num;
        double miv, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] - miv < zero){
                    miv = dis[i], v = i;
                }
            }
            if(fabs((double)inf-miv) < zero){
                printf("oh!\n");
                return;
            }
            else {
                vis[v] = 1, num++, sum += miv;
            }
            for(i = 1; i <= n; i++){
                if(!vis[i] && e[v][i] - dis[i] < zero)
                    dis[i] = e[v][i];
            }
        }
        printf("%.1lf\n", sum*100.0);
    }

[vjudge]: https://vjudge.net/contest/163010#problem/N