C - Building a Space Station——最小生成树_Prim算法

Dear 丶 2022-06-12 14:52 103阅读 0赞

Think:  
1知识点：最小生成树\_Prim算法+浮点数坐标建图  
2题意分析：给定n个点的空间坐标和半径，将n个点直接或间接连通，连通可认为:  
1>两个坐标(作为球理解)重合或覆盖  
2>建立通道将两个坐标(作为球理解)连接，通道长度计算应为表面到表面的直线长度  
3优化思路：题目中自己使用浮点数建图，后续优化可考虑使用实数建图，初始坐标输入的时候将浮点数转化为实数(本题目乘以1000即可)，需要注意的是在求坐标距离的时候注意平方之后求和结果不要超出int范围，可考虑直接强制类型转换为double，进而直接开平方得到浮点数，进而再转化为实数(本题目乘以1000即可)，最终求出连通后的最短总长度再强制类型转换之后再转化为浮点数(除以1000)，认为即可一定程度降低误差

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const double zero = 0.001;
    
    struct Node{
        double x;
        double y;
        double z;
        double r;
    }red[114];
    
    double e[114][114], dis[114];
    int vis[114];
    
    double Dist(int u, int v);
    void Prim(int n);
    
    int main(){
        int n, i, j;
        while(scanf("%d", &n) && n){
            for(i = 1; i <= n; i++){
                scanf("%lf %lf %lf %lf", &red[i].x, &red[i].y, &red[i].z, &red[i].r);
            }
    
            for(i = 1; i <= n; i++){
                e[i][i] = inf;
                for(j = i+1; j <= n; j++){
                    e[i][j] = e[j][i] = Dist(i, j);
                }
            }
    
            Prim(n);
        }
        return 0;
    }
    double Dist(int u, int v){
        double dx = red[u].x - red[v].x;
        double dy = red[u].y - red[v].y;
        double dz = red[u].z - red[v].z;
        double R = dx*dx + dy*dy + dz*dz;
        double dr = sqrt(R);
        dr = dr - red[u].r - red[v].r;
        if(dr < zero)
            return 0.000;
        else
            return dr;
    }
    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.000, num = 1, sum = 0.000;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && miv - dis[i] > zero){
                    miv = dis[i], v = i;
                }
            }
            vis[v] = 1, num++, sum += dis[v];
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] - e[v][i] > zero)
                    dis[i] = e[v][i];
            }
        }
        printf("%.3lf\n", sum);
    }

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