首页 > 代码库 > 并查集——poj2236（带权并查集）
并查集——poj2236（带权并查集）
题目：Wireless Network
题意：给定n台已损坏计算机的位置和计算机最远通信距离d，然后分别根据命令执行以下两种操作：
- "O p" (1 <= p <= N) ：表示修理计算机p；
- "S p q" (1 <= p, q <= N) ：表示检测计算机p和计算机q能否通信。
输出：能通信则输出"SUCCESS"，否则输出"FAIL"
题解：
带权并查集还是那个重要的知识点——关系。
此题，我们使用一个repair数组存储每台电脑的状态（损坏还是好的）
然后就是对每次修好的电脑对其它已经修好的电脑遍历，如果距离小于等于最大通信距离就将他们合并。之后判断2台电脑是不是一个集合中就行了。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
bool repair[1005]; //为真则修好了
struct point{
int pre;
int x,y;
}c[1005];
void init()
{
for(int i=1;i<=n;i++){
c[i].pre = i;
repair[i] = false;
}
}
int find(int x)
{
if(x==c[x].pre) return x;
c[x].pre = find(c[x].pre);
return c[x].pre;
}
void unite(const point p1, const point p2)
{
int root1, root2;
root1 = find(p1.pre);
root2 = find(p2.pre);
if(root1 != root2)
if((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) <= k * k)
c[root2].pre = root1;
}
int main()
{
cin>>n>>k;
init();
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i].x,&c[i].y);
}
char s[5];
int a,b;
while(scanf("%s",s)!=EOF){
if(s[0]==‘O‘){
scanf("%d",&a);
repair[a] = true;
for(int i=1;i<=n;i++){
if(i!=a && repair[i]){
unite(c[a],c[i]);
}
}
}
else{
scanf("%d%d",&a,&b);
if(find(a) == find(b)){
printf("SUCCESS\n");
}
else printf("FAIL\n");
}
}
return 0;
}
并查集——poj2236（带权并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。