[kuangbin带你飞] 题单 最短路问题 + 并查集问题 https://blog.csdn.net/m0_46272108/article/details/108923142
题意： 有一个计算机网络的所有线路都坏了，网络中有n台计算机，现在你可以做两种操作，修理（O）和检测两台计算机是否连通（S），只有修理好的计算机才能连通。连通有个规则，两台计算机的距离不能超过给定的最大距离D（一开始会给你n台计算机的坐标）。检测的时候输出两台计算机是否能连通。 题解： （详情请看代码~~~ ，代码注释写的真的很详细了。）
对并查集不太了解原理的可以看看： https://blog.csdn.net/m0_46272108/article/details/108904480
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long //#define int ll #define INF 0x3f3f3f3f using namespace std; int read() { int w = 1, s = 0; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; //最大公约数 }int gcd(int x,int y) { if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后 //递归终止条件千万不要漏了，辗转相除法 return x % y ? gcd(y, x % y) : y; } int lcm(int x,int y)//计算x和y的最小公倍数 { return x * y / gcd(x, y);//使用公式 } //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------// const int N = 1010; double x[N], y[N];//电脑的坐标x,y int good[N];//已经修好的电脑 int pre[N];//当前电脑的父节点 //n为电脑的数量，d为两台电脑之间能够直接通信的最大距离。 int n, d; int cnt = 0; //返回x的祖宗节点+路径压缩 int find(int x) { //如果当前节点x不是根节点的话，就会往上走一层。 if (pre[x] != x) { pre[x] = find(pre[x]);//就返回父节点的祖宗节点 } return pre[x]; } //集合合并 void join(int a, int b) { //如果两个根节点不相同的话 if (find(a) != find(b)) { //连通 pre[find(a)] = find(b); } } //两台电脑之间的距离 double dis( int i, int j ) { return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); } int main() { n = read(), d = read(); for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i]; } for (int i = 1; i <= n; ++i) { pre[i] = i; } int a, b; char op; while(cin >> op){ //读入操作 if (op == 'O') { a = read(); for(int i = 0; i < cnt; ++i) { //如果两个点的距离小于d，则直接连通 if (dis(a, good[i]) <= d) { join (a, good[i]); } } //a是修好的电脑 good[cnt++] = a; } else if (op = 'S') { a = read(), b = read(); //判断a和b是否处于同一个连通块。 if (find(a) == find(b)) { printf("SUCCESS\n"); } else { printf("FAIL\n"); } } } return 0; }