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