A
地震发生在东南亚。ACM（亚洲合作医疗团队）已经与膝上电脑建立了无线网络，但是一次意外的余震袭击，网络中的所有计算机都被打破了。计算机一个接一个地修复，网络逐渐开始工作。由于硬件限制，每台计算机只能直接与距离它不远的计算机进行通信。但是，每台计算机都可以被视为两台计算机之间通信的中介，也就是说，如果计算机A和计算机B可以直接通信，或者计算机C可以与A和A进行通信，则计算机A和计算机B可以进行通信。 B.
在修复网络的过程中，工作人员可以随时进行两种操作，修复计算机或测试两台计算机是否可以通信。你的工作是回答所有的测试操作。
输入
第一行包含两个整数N和d（1 <= N <= 1001,0 <= d <= 20000）。这里N是计算机的数量，编号从1到N，D是两台计算机可以直接通信的最大距离。在接下来的N行中，每行包含两个整数xi，yi（0 <= xi，yi <= 10000），这是N台计算机的坐标。从第（N + 1）行到输入结束，有一些操作，这些操作是一个接一个地执行的。每行包含以下两种格式之一的操作：
1。“O p”（1 <= p <= N），表示修复计算机p。
2.“S p q”（1 <= p，q <= N），这意味着测试计算机p和q是否可以通信。
输入不会超过300000行。
产量
对于每个测试操作，如果两台计算机可以通信则打印“SUCCESS”，否则打印“FAIL”。
样本输入
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
样本输出
失败的
成功题意：就是先给出电脑数目N，然后就是给出N个顶点的位置。然后告诉你两个顶点之间距离小于d才能算作联通，如果dis(a,b)<d,则ab是属于联通的，如果dis（ab)<d&&dis(bc)<d,那么ac是属于联通的。然后每次修复一个点就查询是否与之前的点联通，如果联通那就是他们在同一个树上，具有联通关系。father数组初始化都是自身。自身属于一棵树，然后再进行合并，find函数找到该点的根节点，根节点的特点是father[i]=i，然后如果两个根节点不相等，但是两个顶点之间是具有联通关系的。那么就合并树。father[find[x]]=find[y]。查询就是查询两个根节点是否相等。
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;#define MAXN 1010int dx[MAXN],dy[MAXN]; //坐标
int par[MAXN]; //par[x]表示x的父节点
int repair[MAXN] ={0};
int n;void Init() //初始化
{int i;for(i=0;i<=n;i++)par[i] = i;
}int Find(int x) //查询x的根节点并路径压缩
{if(par[x]!=x)par[x] = Find(par[x]);return par[x];
}void Union(int x,int y) //合并x和y所在集合
{par[Find(x)] = Find(y);
}int Abs(int n)
{return n>0?n:-n;
}double Dis(int a,int b)
{return sqrt( double(dx[a]-dx[b])*(dx[a]-dx[b]) + (dy[a]-dy[b])*(dy[a]-dy[b]) );
}int main()
{int d,i;//初始化scanf("%d%d",&n,&d);Init();//输入坐标for(i=0;i<n;i++){scanf("%d%d",&dx[i],&dy[i]);}//操作char cmd[2];int p,q,len=0;while(scanf("%s",cmd)!=EOF){switch(cmd[0]){case 'O':scanf("%d",&p);p--;repair[len++] = p;for(i=0;i<len-1;i++) //遍历所有修过的计算机，看能否联通if( repair[i]!=p && Dis(repair[i],p)<=double(d) )Union(repair[i],p);break;case 'S':scanf("%d%d",&p,&q);p--,q--;if(Find(p)==Find(q)) //是否有路printf("SUCCESS\n");else printf("FAIL\n");default:break;}}return 0;
}
发布评论