A - Wireless Network ——并查集

62 阅读 0 评论 41 点赞

我是靠谱客的博主哭泣钢铁侠，最近开发中收集的这篇文章主要介绍A - Wireless Network ——并查集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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("SUCCESSn");
            else
                printf("FAILn");
        }
    }
    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];
    }
}