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

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

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

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

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);
}