POJ 2236 Wireless Network
浏览数：51 /
时间：2015年06月09日
思路详见课本 P 213
思路：直接用并查集，最后看 p 和 q 是否 在一个 集合中 即可。属于同一集合，则 可以通信；否则失败。
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000 +100;
int set[maxn];
int xx[maxn];
int yy[maxn];
bool valid[maxn];
int n,d;
int set_find(int d)//路径压缩的 合并树根 的函数
{
if(set[d]<0)
return d;
return set[d]=set_find(set[d]);
}
void join(int x,int y)
{
x=set_find(x);
y=set_find(y);
if(x!=y)//-----------此处这个判断千万不能少，否则在 set_find()函数中，出现死循环（由于节点 自己 指向 自己，找不到 结束条件 （即树根））
//------------提交会出现runtime error
set[x]=y;
}
int in(int i,int p)//判断i 是否在 p的范围内
{
if( (xx[i]-xx[p]) * (xx[i]-xx[p]) + (yy[i]-yy[p]) * (yy[i]-yy[p]) <= d*d )
return 1;
return 0;
}
void repair(int p)//修复 p
{
valid[p]=1;
int i;
for(i=1;i<=n;i++)
if( valid[i] &&in(i,p) &&i!=p)
join(i,p);
}
void search(int p,int q) //查看 p 和 q是否 可以 通信
{
if( set_find(p)==set_find(q) )
cout<<"SUCCESS"<<endl;
else
cout<<"FAIL"<<endl;
}
int main()
{
memset(set,-1,sizeof(set));
memset(xx,0,sizeof(xx));
memset(yy,0,sizeof(yy));
memset(valid,0,sizeof(valid));
cin>>n>>d;
int i;
for(i=1;i<=n;i++)
cin>>xx[i]>>yy[i];
char c;
while(cin>>c)
{
if(c==‘O‘)
{
int p;
cin>>p;
repair(p);
}
else if(c==‘S‘)
{
int p,q;
cin>>p>>q;
search(p,q);
}
}
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
