欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

noip 并查集

程序员文章站 2022-05-22 13:36:51
...

原理

见wiki
https://zh.wikipedia.org/wiki/并查集

代码

并查集的原理不难理解,主要是如何把现实问题描述为计算机问题,这就考计算机思维了,说白了就是多刷题。

并查集代码模版有3个函数,模版依据noip 2017 奶酪,具体需根据题意更改。

//下标作为结点
int father[MAX];//下标的父节点
int rank[MAX];//下标的秩

inline void make_set(int x)
{
    father[x] = x;
    rank[x] = 0;
}

int find_set(int x)
{
    if(x != father[x]){
        father[x] = find_set(father[x]);
    }
    return father[x];
}

void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y){
        return;
    }
    if(rank[x] > rank[y]){
        father[y] = x;
    }else{
        if(rank[x] == rank[y]){
            ++rank[y];
         }
        father[x] = y;
    }   
}

这些都是经过优化过的代码,优化有2方面
1. find_set中的路径压缩
2. union_set中的按秩合并

不过经过我的测试,noip中不需要优化完全可以AC,具体如下:

int father[MAX];

inline void make_set(int x)
{
    father[x] = x;
}

//
int find_set(int x)
{
    if(x != father[x]){
        father[x] = find_set(father[x]);
    }
    return father[x];
}
//不进行路径压缩 需根据题意具体分析
int find_set(int x)
{
    if(x != father[x]){
        return find_set(father[x]);
    }
    return father[x];
}
//非递归形式 需根据题意具体分析
int find_set(int x)
{
    int i=x;
    for(; i != father[i]; i=father[i]);

    return i;
}

void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y){
        return;
    }

    father[x] = y;
}

具体题目的代码如下,未优化版本可以通过,不过如果不用库文件math,可能会超时,所以库math经过了优化。

#include <cstdio>
#include <cmath>

#define MAX 1005

int father[MAX];
int rank[MAX];

inline void make_set(int x)
{
    father[x] = x;
    rank[x] = 0;
}

int find_set(int x)
{
    if(x != father[x]){
        father[x] = find_set(father[x]);
    }
    return father[x];
}

void union_set(int x, int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x == y){
        return;
    }
    if(rank[x] > rank[y]){
        father[y] = x;
    }else{
        if(rank[x] == rank[y]){
            ++rank[y];
         }
        father[x] = y;
    }   
}

int t,n;
long long h,r;
long long x[MAX],y[MAX],z[MAX];

inline long long dis(int u,int v)
{
    return sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])+(z[u]-z[v])*(z[u]-z[v]));
}

int main()
{
    //freopen("cheese.in","r",stdin);
    //freopen("cheese.out","w",stdout);
    scanf("%d",&t);
    for(int i=1; i<=t; ++i){
        scanf("%d%lld%lld",&n,&h,&r);
        for(int j=1; j<=n; ++j){
            scanf("%lld%lld%lld",&x[j],&y[j],&z[j]);
        }

        for(int j=0; j<=n+1; ++j){
            make_set(j);
        }

        for(int j=1; j<=n; ++j){
            if(z[j]+r >= h){
                union_set(j,n+1);
            }
            if(z[j]-r <= 0){
                union_set(j,0);
            }
        }

        for(int j=1; j<=n; ++j){
            for(int k=j+1; k<=n; ++k){
                if(dis(j,k) <= 2*r){
                    union_set(j,k);
                }
            }
        }

        if(find_set(0) == find_set(n+1)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }

    }

    return 0;
}
相关标签: noip