A - Wireless Network ——并查集

雨点打透心脏的1/2处 2022-06-12 11:14 181阅读 0赞

Think:  
1知识点：并查集  
2题意分析：初始状态已知n台电脑坐标，以及电脑连接的最大距离，进而，2种操作，操作O将电脑u连接到可连接集合，操作S询问电脑u和电脑v是否在同一集合  
3解题思路：预处理各台电脑与其它电脑的距离，标记已修复电脑，操作O枚举并通过并查集连接可与电脑u连接的电脑，操作S通过并查集进行判断是否在同一集合  
4优化思路：将可连接坐标预处理并通过前向星记录可与当前结点连接的结点

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N = 1e3 + 4;
    
    struct Coordinate{
        int x;
        int y;
    }coor[N];
    
    int n, d, f[N], vis[N];
    double e[N][N];
    
    void Init();
    int get_f(int v);
    void Merge(int u, int v);
    double dist(int u, int v);
    
    int main(){
        int i, j, u, v;
        char st[4];
        scanf("%d %d", &n, &d);
        for(i = 1; i <= n; i++){
            scanf("%d %d", &coor[i].x, &coor[i].y);
        }
        for(i = 1; i <= n; i++){
            e[i][i] = 0;
            for(j = 1; j < i; j++){
                e[i][j] = e[j][i] = dist(i, j);
            }
        }
    
        Init();
        memset(vis, 0, sizeof(vis));
        while(~scanf("%s", st)){
            if(st[0] == 'O'){
                scanf("%d", &u);
                vis[u] = 1;
                for(i = 1; i <= n; i++){
                    if(e[u][i] <= d && vis[u] && vis[i]){
                        Merge(u, i);
                    }
                }
            }
            else if(st[0] == 'S'){
                scanf("%d %d", &u, &v);
                if(get_f(u) == get_f(v))
                    printf("SUCCESS\n");
                else
                    printf("FAIL\n");
            }
        }
        return 0;
    }
    double dist(int u, int v){
        double dx = coor[u].x - coor[v].x;
        double dy = coor[u].y - coor[v].y;
        return sqrt(dx*dx + dy*dy);
    }
    void Init(){
        for(int i = 1; i <= n; i++){
            f[i] = i;
        }
    }
    void Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        f[t2] = t1;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        else {
            f[v] = get_f(f[v]);
            return f[v];
        }
    }

[vjudge]: https://vjudge.net/contest/163007#problem/A