行了这是个裸的判联通的题，dfs bfs 并查集均可
这是并查集的做法
#include <bits/stdc++.h> using namespace std; const double eps = 1e-8; const int maxn = 1e3 + 10; int sgn(double x) { if (fabs(x) < eps) return 0; else return x > 0 ? 1 : -1; } int n; double r; double x[maxn], y[maxn]; int fa[maxn]; void Init() {for (int i = 0; i < maxn; ++i) fa[i] = i;} int find(int X) {return X == fa[X] ? fa[X] : fa[X] = find(fa[X]);} void Unin(int X, int Y) { X = find(X); Y = find(Y); if (X != Y) { fa[X] = Y; } } double dis(int i, int j) { return hypot(x[i] - x[j], y[i] - y[j]); } int main() { int t; scanf("%d", &t); while (t--) { Init(); scanf("%d %lf", &n, &r); r *= 2.0; for (int i = 1; i <= n; ++i) { scanf("%lf %lf", x + i, y + i); } for (int i = 1; i <= n; ++i) { if (sgn(x[i] - r) <= 0) { Unin(0, i); } if (sgn(100 - x[i] - r) <= eps) { Unin(i, n + 1); } } for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { if (sgn(dis(i, j) - r) <= 0) { Unin(i, j); } } } puts(find(0) != find(n + 1) ? "Yes" : "No"); } return 0; }dfs做法
#include <bits/stdc++.h> #include<vector> using namespace std; typedef long long LL; typedef pair<double, double> pdd; const int N = 1e3 + 10; const int M = 2e6 + 10; const int inf = 0x3f3f3f3f; const double eps = 1e-5; double x[N]; double y[N]; vector<int> G[N]; bool vis[N]; bool dfs(int u) { vis[u]=true; if(!u) return true; vector<int>::iterator it; for(it=G[u].begin();it!=G[u].end();it++) if(!vis[*it]) if(dfs(*it))return true; return false; } int main() { int T;cin>>T; for (;T--;) { int n; double r; scanf("%d%lf",&n,&r); for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); double d=2*r,d2=d*d; if (d >= 100) { puts("No"); continue; } for (int i = 1; i <= n; i++) { if (x[i] <= d) { G[0].push_back(i); G[i].push_back(0); } if (100 - x[i] <= d) { G[n + 1].push_back(i); G[i].push_back(n + 1); } } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { double f = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); if (f - d2 <= eps) { G[i].push_back(j); G[j].push_back(i); } } } if (dfs(n + 1)) puts("No"); else puts("Yes"); for (int i = 0; i <= n + 1; i++) { G[i].clear(); vis[i] = false; } } return 0; }bfs 牛客网copy的己卯年三月十二 的代码
#include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <vector> #include <algorithm> #include <queue> #include<bits/stdc++.h> #include <stdlib.h> using namespace std; #define ull unsigned long long #define ll long long typedef pair<int,int> pii; typedef pair<double,double> pdd; typedef pair<double,int> pdi; const int maxn=1e3+5; const double eps=1e-8; pdd a[maxn]; int n,vis[maxn]; double r; vector<int> G[maxn]; bool touchL(int x){ return a[x].first-2.0*r<eps; } bool touchR(int x){ return 100.0-a[x].first-2.0*r<eps; } bool touch(int x,int y){ double dx=a[x].first-a[y].first,dy=a[x].second-a[y].second; return dx*dx+dy*dy-4.0*r*r<eps; } bool bfs(void){ if(100.0-2.0*r<eps) return false; queue<int> q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;++i)if(touchL(i)) q.push(i),vis[i]=1; if(q.empty()) return true; while(!q.empty()){ int u=q.front();q.pop(); if(touchR(u)) return false; for(int i=0;i<G[u].size();++i)if(!vis[G[u][i]]){ int v=G[u][i];vis[v]=1; q.push(v); } } return true; } int main(void){ int T;scanf("%d",&T); while(T--){ scanf("%d%lf",&n,&r); for(int i=1;i<=n;++i){ G[i].clear(); scanf("%lf%lf",&a[i].first,&a[i].second); } for(int i=1;i<=n;++i) for(int j=1;j<i;++j)if(touch(i,j)){ G[i].push_back(j);G[j].push_back(i); } if(bfs()) puts("Yes"); else puts("No"); } return 0; }
