[C++知识库]POJ2236题解

这道题可以说是并查集板子题了

我们做一个初始化：

我们把每一台电脑看做一个点，我们将每一个点与它能通信的点连一条边

就是代码里的这一段

for(register int i=1;i<n;i++){
	for(register int j=i+1;j<=n;j++){
		double x1=x[i],x2=x[j],y1=y[i],y2=y[j];
		if(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))<=d){
			e[i].push_back(j);
			e[j].push_back(i);
		}
	}
}

然后跑一遍并查集：

做 "O" 操作的时候把修复好的电脑与其他可通信范围内的好电脑并集，有了前面的初始化，这里就不用一个个枚举了（本人表达能力不好，说话有点绕）

在做 "S" 操作的时候就判断他们两个是否在同一个集合里

AC代码?

?#include<algorithm>
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

const int N=1009;

int n,d,x[N],y[N],f[N],p,q;//x记x坐标,y记y坐标,f[i]记i的父亲
char c;
bool vis[N];//vis记它有没有被修复,0表示没有,1表示有

vector<int>e[N];//e[x][j]=y表示x有一条边到边y,且是第j条边

int find(int x){ //找到x所在集合的根
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}

int main(){
	scanf("%d%d",&n,&d);
	
	for(register int i=1;i<=n;i++)f[i]=i;//初始化f,个人喜欢这么写
	
	for(register int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	
	for(register int i=1;i<n;i++) //初始化
		for(register int j=i+1;j<=n;j++){
			double x1=x[i],x2=x[j],y1=y[i],y2=y[j];
			if(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))<=d){
				e[i].push_back(j);
				e[j].push_back(i);
			}
		}
	
	while(cin>>c){
		if(c=='0'||c=='O'){
			scanf("%d",&p);
			vis[p]=1;
			for(register int i=0;i<e[p].size();i++)
				if(vis[e[p][i]])
					f[find(e[p][i])]=find(p);
		}
		else{
			scanf("%d%d",&p,&q);
			if(find(p)==find(q))printf("SUCCESS\n");
			else printf("FAIL\n");
		}
	}
	return 0;
}

谢谢?