POJ 2236 Wireless Network
算起来是个并查集问题。
题意是说 有N台电脑,每台电脑能以自身为中心连接D米范围的电脑。
给出N台电脑坐标,针对询问操作,输出是否连通。
我用邻接表存储的,如果两电脑坐标 距离小于他们半径和,存起来,表明这两个点可以连通。
用 online[] 表明是否被修复。 修复之后才可以用并查集合并。
修复操作就启用 online,然后遍历这个点的邻接边,如果也有online 的,就合并。
之后就是针对询问 输出。在一个集合就SUCCESS
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n; double r; vector<int>g[1001]; int fa[1001]; bool online[1001]; struct node { double x,y; } point[1001]; int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } double getlen(node a,node b) { double len=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)); return len-r; } int main() { scanf("%d%lf",&n,&r); for(int i=1; i<=n; i++) scanf("%lf%lf",&point[i].x,&point[i].y); for(int i=1; i<=n; i++) fa[i]=i,g[i].clear(); int cot=0; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) { double len=getlen(point[i],point[j]); if(len<=0) { g[i].push_back(j); g[j].push_back(i); } } memset(online,0,sizeof(online)); char str[10]; while(scanf("%s",str)!=EOF) { if(str[0]=='S') { int a,b; scanf("%d%d",&a,&b); if(father(a)!=father(b)) puts("FAIL"); else puts("SUCCESS"); } else if(str[0]=='O') { int u; scanf("%d",&u); online[u]=1; for(int j=0; j<g[u].size(); j++) { int v=g[u][j]; if(!online[v])continue; v=father(v); if(u==v)continue; fa[v]=u; } } } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。