G - Arctic Network ——最小生成树+double精度+优先队列

╰+哭是因爲堅強的太久メ 2022-06-11 06:06 141阅读 0赞

Think:  
1知识点：最小生成树+double精度+优先队列  
2题意分析：现在需要连接我方哨点，两种电子连接方式，第一种卫星信号，任意距离，第二种电台信号，有距离限制，因考虑后期维护需要确定所有用电台连接的哨点中信号联系最大距离，第一行输入测试组数n,每组测试数据第一行输入S(\[1, 100\])和P((S, 500\]),代表可用卫星信号连接的哨点数量和总的哨点数量，之后P行x, y(0 <= x, y <= 10000)表示哨点1~P的坐标位置表示，Prim算法连接P个哨点，记录连接的距离，进而从大到小排序(或记录时直接通过优先队列有序化)选取第S个距离

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——第S个距离不代表第S个大的距离

#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;
    }node[514];
    
    int vis[514];
    double e[514][514], dis[514];
    
    void Prim(int S, int P);
    double Dis(int u, int v);
    
    int main(){
        int T, S, P, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &S, &P);
            for(i = 1; i <= P; i++)
                scanf("%lf %lf", &node[i].x, &node[i].y);
            for(i = 1; i <= P; i++){
                e[i][i] = 0.0;
                for(j = i+1; j <= P; j++){
                    e[i][j] = e[j][i] = Dis(i, j);
                }
            }
            Prim(S, P);
        }
        return 0;
    }
    double Dis(int u, int v){
        double dx = node[u].x - node[v].x;
        double dy = node[u].y - node[v].y;
        double D = dx*dx + dy*dy;
        return sqrt(D);
    }
    void Prim(int S, int P){
        int i, v, num;
        double miv, ans;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= P; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0.00, num = 1, ans = 0.00;
        while(num < P){
            miv = inf;
            for(i = 1; i <= P; i++){
                if(!vis[i] && dis[i]-miv < zero){
                    v = i, miv = dis[i];
                }
            }
            vis[v] = 1, num++;
            if(S) S--;
            else {
                ans = max(ans, miv);
            }
            for(i = 1; i <= P; i++){
                if(!vis[i] && e[v][i]-dis[i] < zero)
                    dis[i] = e[v][i];
            }
        }
        printf("%.2lf\n", ans);
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const double zero = 0.001;
    
    struct Node{
        double x;
        double y;
    }node[514];
    
    int vis[514];
    double e[514][514], dis[514];
    
    void Prim(int S, int P);
    double Dis(int u, int v);
    
    int main(){
        int T, S, P, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &S, &P);
            for(i = 1; i <= P; i++)
                scanf("%lf %lf", &node[i].x, &node[i].y);
            for(i = 1; i <= P; i++){
                e[i][i] = 0.0;
                for(j = i+1; j <= P; j++){
                    e[i][j] = e[j][i] = Dis(i, j);
                }
            }
            Prim(S, P);
        }
        return 0;
    }
    double Dis(int u, int v){
        double dx = node[u].x - node[v].x;
        double dy = node[u].y - node[v].y;
        double D = dx*dx + dy*dy;
        return sqrt(D);
    }
    void Prim(int S, int P){
        int i, v, num;
        double miv, ans;
        priority_queue <double> q;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= P; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0.00, num = 1, ans = 0.00;
        while(num < P){
            miv = inf;
            for(i = 1; i <= P; i++){
                if(!vis[i] && dis[i]-miv < zero){
                    v = i, miv = dis[i];
                }
            }
            vis[v] = 1, num++;
            q.push(miv);
            for(i = 1; i <= P; i++){
                if(!vis[i] && e[v][i]-dis[i] < zero)
                    dis[i] = e[v][i];
            }
        }
        S -= 1;
        while(!q.empty()){
            double t1 = q.top();
            q.pop();
            if(S) S--;
            else {
                ans = t1;
                break;
            }
        }
        printf("%.2lf\n", ans);
    }

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