并查集实现

本来想构建一张无向图然后dijkstra，后来觉得只判断连通性用dijkstra太浪费算力，没必要，于是用并查集实现。

注意：所有涉及long long范围的运算都必须用long long变量，int计算后存long long是不行的，我已经被坑了

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 1005
using namespace std;

int ufs[MAXN];
unsigned long long x[MAXN], y[MAXN], z[MAXN];

void init(int n){
  for(int i=0; i<=n; i++){
    ufs[i] = i;
  }
  return;
}

int find(int a){
  int rt = a, trt = a, ttrt;
  while(rt != ufs[rt]){
    rt = ufs[rt];
  }
  while(trt != ufs[trt]){
    ttrt = trt;
    trt = ufs[trt];
    ufs[ttrt] = rt;
  }
  return rt;
}

void unite(int a, int b){
  // cout << "Unite " << a << " " << b << endl;
  int rta, rtb;
  rta = find(a);
  rtb = find(b);
  ufs[rtb] = rta;
  return;
}

unsigned long long getdsq(int i, int j){
  return (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]) + (z[i] - z[j])*(z[i] - z[j]);
}

bool sameufs(int a, int b){
  return find(a) == find(b);
}

int main(){
  int t, n, h;
  unsigned long long r, rr, d;
  cin >> t;
  for(int roun=0; roun<t; roun++){
    cin >> n >> h >> r;
    init(n+1);
    rr = r*r*4;
    for(int i=1; i<=n; i++){
      cin >> x[i] >> y[i] >> z[i];
      if(z[i] <= r){
        unite(0, i);
      }
      if(z[i] + r >= h){
        unite(n+1, i);
      }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
          if(i != j){
            d = getdsq(i, j);
            // cout << d << " " << r*r << endl;
            if(d <= rr){
              unite(i, j);
            }
          }
        }
    }
    if(sameufs(0, n+1)){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
  return 0;
}

评测情况

Accepted

#   状态  耗时  内存占用
#1  Accepted    3ms     256.0 KiB
#2  Accepted    2ms     384.0 KiB
#3  Accepted    2ms     256.0 KiB
#4  Accepted    2ms     384.0 KiB
#5  Accepted    21ms    256.0 KiB
#6  Accepted    32ms    368.0 KiB
#7  Accepted    91ms    384.0 KiB
#8  Accepted    58ms    384.0 KiB
#9  Accepted    119ms   384.0 KiB
#10     Accepted    73ms    384.0 KiB

#1 Accepted 3ms 368.0 KiB
#2 Accepted 4ms 368.0 KiB
#3 Accepted 3ms 352.0 KiB
#4 Accepted 3ms 356.0 KiB
#5 Accepted 5ms 384.0 KiB
#6 Accepted 8ms 384.0 KiB
#7 Accepted 21ms 384.0 KiB
#8 Accepted 24ms 364.0 KiB
#9 Accepted 23ms 356.0 KiB
#10 Accepted 12ms 384.0 KiB

本题多种方法、我写了三种，bfs，dfs，并查集
考试的时候还是个渣，不知道dfs还能不回溯，所以一行回溯把我的满分代码压到了30分。
下面代码是dfs，只需要处理连通性。
dfs同理
注意想要不失精的话不能开根号，那么是爆longlong的，开unsigned即可
当然，还有奇葩的方法，比如跑一个tarjan、做一次spfa（极大值则非联通,可以在天上和地下建立超级原点）
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll x[1100],y[1100],z[1100];
ll n,h,r;
bool used[1001];
bool flag;
unsigned long long dis(int i,int j)
{
return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
}
void dfs(int idx)
{
if(z[idx]+r>=h)
{
flag=1;
return;
}
used[idx]=1;
for(int i=1;i<=n;i++)
{
if(flag==1)return;
if(!used[i]&&dis(idx,i)<=4*r*r)
dfs(i);
}
}
int main()
{
int t;
scanf("%d",&t);
for(int tt=1;tt<=t;tt++)
{

flag=0;
memset(used,0,sizeof(used));

scanf("%d%d%d",&n,&h,&r);
for(int i=1;i<=n;i++)
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
for(int i=1;i<=n;i++)
if(z[i]<=r)dfs(i);
if(flag)printf("Yes\n");
else printf("No\n");

}

}
```

这是一道很裸的搜索题 别的做法也有(如并查集之类)
但最简单的方法只需要朴素的bfs即可
我们只需要做两件事
判断每两点之间是否可达以及哪些点是可以第一个到达和哪些点是可以到达上表面的
这样的话我们就相当于建立了一张隐式图
然后我们直接进行**bfs**
注意因为是判断可达性
每个点只需要判断一次就好了（即只需要进入一次队列）
那我们需要用vis来判重
这样的复杂度是很低的
同时注意数据大小 开个ULL就好了
直接开方也没被卡精度TAT

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using namespace std;

char rd;    int pn;
template<typename Type>
inline void read(Type& v)
{
    pn=1;
    while((rd=getchar())<'0'||rd>'9')
        if(rd=='-')
            pn=-1;
    v=rd-'0';
    while((rd=getchar())>='0'&&rd<='9')
        v=v*10+rd-'0';
    v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
    if(v==0)
        putchar(48);
    else  
    {
        if(v<0)
        {
            putchar('-');
            v=-v;
        }
        int len=0,dg[20];  
        while(v>0)
        {
            dg[++len]=v%10;
            v/=10;
        }  
        for(int i=len;i>=1;i--)
            putchar(dg[i]+48);  
    }
    if(c)
        putchar('\n');
    else
        putchar(' ');
}

#define LL unsigned long long
const int MAXN=1005;
struct point
{
    LL sx,sy,sz;
}p[MAXN];
bool can_arrive[MAXN];
bool vis[MAXN];
int g[MAXN][MAXN];
int t,n;
LL h,r;

void init()
{
    read(n);
    read(h);    read(r);
    memset(vis,0,sizeof(vis));
    memset(can_arrive,0,sizeof(can_arrive));
    memset(g,0,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        read(p[i].sx);
        read(p[i].sy);
        read(p[i].sz);
    }
}

bool right(int i,int j)
{
    long double d=sqrt((p[i].sx-p[j].sx)*(p[i].sx-p[j].sx)+(p[i].sy-p[j].sy)*(p[i].sy-p[j].sy)+(p[i].sz-p[j].sz)*(p[i].sz-p[j].sz));
    return d<=2*r;
}

void work()
{
    for(int i=1;i<=n;i++)
        if(p[i].sz+r>=h)
            can_arrive[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(right(i,j))
                g[i][j]=g[j][i]=1;
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(p[i].sz<=r)
        {
            q.push(i);
            vis[i]=1;
        }
    while(!q.empty())
    {
        int u=q.front();    q.pop();
        if(can_arrive[u])
        {
            printf("Yes\n");
            return;
        }
        for(int i=1;i<=n;i++)
            if(g[u][i]&&!vis[i])
            {
                q.push(i);
                vis[i]=1;
            }
    }
    printf("No\n");
    return;
}

int main()
{
    read(t);
    while(t--)
    {
        init();
        work();
    }
    return 0;
}
     

Accepted

状态 耗时 内存占用

#1 Accepted 12ms 4.23 MiB
#2 Accepted 12ms 4.223 MiB
#3 Accepted 13ms 4.25 MiB
#4 Accepted 19ms 4.234 MiB
#5 Accepted 40ms 4.238 MiB
#6 Accepted 73ms 4.23 MiB
#7 Accepted 117ms 4.125 MiB
#8 Accepted 111ms 4.23 MiB
#9 Accepted 102ms 4.215 MiB
#10 Accepted 109ms 4.23 MiB