poj 2236 Wireless Network 并查集

2021-03-19 13:26

阅读：568

标签：ref system 两台 size char 标记 mil net clu

链接：http://poj.org/problem?id=2236

并查集水题，+距离约束

题意：

东南亚发生地震。亚洲合作医疗队（ACM）已与膝上计算机建立了无线网络，但由于意外的余震袭击，网络中的所有计算机都被破坏了。电脑被一一修复，网络逐渐恢复工作。由于硬件限制，每台计算机只能直接与不超过d米的计算机通信。但是，每台计算机都可以视为其他两台计算机之间通信的中介，也就是说，如果计算机A和计算机B可以直接通信，或者有计算机C可以同时与A和B通信，则计算机A和计算机B可以通信。 B．

在修复网络的过程中，工作人员可以随时执行两种操作：修复计算机，或测试两台计算机是否可以通信。您的工作是回答所有测试操作。

刚开始所有的都是断的用vis标记下；

code：

#include

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int n,d;

int fa[maxn],vis[maxn];

struct node

{

double x,y;

}a[maxn];

double dist(node a,node b)

{

double temp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);

return sqrt(temp);

}

int Find(int x)

{

return x==fa[x]?x:fa[x]=Find(fa[x]);

}

void Union(int x,int y)

{

int fx=Find(x),fy=Find(y);

if(fx!=fy&&dist(a[x],a[y])

fa[fx]=fy;

}

void init()

{

for(int i=0; i

{

fa[i]=i;

vis[i]=0;

}

int main()

{

scanf("%d%d",&n,&d);

init();

for(int i=1; i

scanf("%lf%lf",&a[i].x,&a[i].y);

char ch;

int x,y;

while(cin>>ch)

{

if(ch==‘O‘)

{

scanf("%d",&x);

vis[x]=1;

for(int i=1; i

{

if(vis[i])

Union(x,i);

}

else

{

scanf("%d%d",&x,&y);

if(Find(x)==Find(y))

printf("SUCCESS\n");

else

printf("FAIL\n");

}

// system("pause");

return 0;

}


/*

4 1

FAIL
SUCCESS

*/

poj 2236 Wireless Network 并查集

标签：ref system 两台 size char 标记 mil net clu

原文地址：https://www.cnblogs.com/sweetlittlebaby/p/12752639.html

上一篇：解决项目迁移至Kubernetes集群中的代理问题

下一篇：jQuery学习 (固定导航栏效果)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：poj 2236 Wireless Network 并查集
文章链接：http://soscw.com/index.php/essay/66259.html

亲，登录后才可以留言！

poj 2236 Wireless Network 并查集

评论

热门文章

推荐文章

最新文章

置顶文章