POJ-2236-Wireless Network-白红宇

POJ-2236-Wireless Network

阅读量：6801 次

发布时间：2019-06-26

本文共 1624 字，大约阅读时间需要 5 分钟。

链接：https://vjudge.net/problem/POJ-2236#author=0

题意：

南亚发生了一次地震。ACM (Asia Cooperated Medical 亚洲联合医疗队) 已经为膝上型电脑搭建了一个无线网络，但受到了一次不可预知的余震攻击，因此网络中的所有电脑都被破坏了。电脑被逐台修复，网络逐步恢复了工作。由于受到硬件的约束，每台电脑只能与距离它不超过 d 米的其它电脑直接通信。但每台电脑可被看作其它两台电脑的通信中转点，也就是说，如果电脑 A 和电脑 B 可以直接通信，或存在一台电脑 C 既可与 A 也可与 B 通信，那么电脑 A 和电脑 B 之间就能够通信。

在处理网络修复的过程中，工作人员们在任何一个时刻，可以执行两种操作：维修一台电脑，或测试两台电脑是否能够通信。请您找出全部的测试操作。

思路：

并查集，先处理输入的结点。用vector保存每个结点可以直接连接的点。

每次修复，将查找结点的连接点，将修复过的找到父节点，并令其父亲为当前修复的。

判断联通直接查找父节点即可。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;const int MAXN = 10100;int n,d;struct Node{ double _x; double _y;}node[MAXN];vector
                
                  member[MAXN];int Father[MAXN];int Vis[MAXN];double Get_Len(Node a,Node b){ return sqrt((a._x-b._x)*(a._x-b._x) + (a._y-b._y)*(a._y-b._y));}int Get_F(int x){ return Father[x] = Father[x] == x ? x:Get_F(Father[x]); if (Father[x] == x) return x; else { Father[x] = Get_F(Father[x]); return Father[x]; }}int main(){ scanf("%d%d",&n,&d); for (int i = 1;i<=n;i++) scanf("%lf%lf",&node[i]._x,&node[i]._y); for (int i = 1;i<=n;i++) { Father[i] = i; for (int j = 1; j <= n; j++) if (i != j && Get_Len(node[i], node[j]) <= d) member[i].push_back(j); } //构造 string s; while (cin >> s) { if (s[0] == 'S') { int a,b; scanf("%d%d",&a,&b); int ta = Get_F(a); int tb = Get_F(b); if (ta == tb) printf("SUCCESS\n"); else printf("FAIL\n"); } else { int a,b; scanf("%d",&a); Vis[a] = 1; for (int i = 0;i

转载于:https://www.cnblogs.com/YDDDD/p/10295838.html

你可能感兴趣的文章