博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 2236 A - Wireless Network[kuangbin带你飞]专题五 并查集
阅读量:5825 次
发布时间:2019-06-18

本文共 3224 字,大约阅读时间需要 10 分钟。

A - Wireless Network
Time Limit:10000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u
     

Description

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B. 
In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations. 

Input

The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats: 
1. "O p" (1 <= p <= N), which means repairing computer p. 
2. "S p q" (1 <= p, q <= N), which means testing whether computer p and q can communicate. 
The input will not exceed 300000 lines. 

Output

For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" if not.

Sample Input

4 10 10 20 30 4O 1O 2O 4S 1 4O 3S 1 4

Sample Output

FAILSUCCESS

题目大意:

一张图上分布着n台坏了的电脑,并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网,也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x,给出操作“S x y”,请你判断x和y在此时有没有连接上。

解题思路:

这是一个简单的并查集,只是需要判断一下距离是不是满足条件就行了

基本上是模板:

直接贴代码:

/**2015 - 09 - 18 晚上Author: ITAKMotto:今日的我要超越昨日的我,明日的我要胜过今日的我,以创作出更好的代码为目标,不断地超越自己。**/#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const int maxn = 1005;const double eps = 1e-7;struct node{ int x, y;} arr[maxn];int rank[maxn], fa[maxn], num[maxn];///基本上是模板void Init(int x){ for(int i=1; i<=x; i++) { fa[i] = i; rank[i] = 0; }}int Find(int x){ if(fa[x] != x) fa[x] = Find(fa[x]); return fa[x];}void Union(int x, int y){ int fx = Find(x), fy = Find(y); if(fx == fy) return; if(rank[fx] > rank[fy]) fa[fy] = fx; else { fa[fx] = fy; if(rank[fx] == rank[fy]) rank[fy]++; }}///计算距离(x 与 y)int Dis(node A, node B){ return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);}char str[20];int main(){ int m, d, xx, yy; scanf("%d%d",&m, &d); Init(m); for(int i=1; i<=m; i++) scanf("%d%d",&arr[i].x, &arr[i].y); int cnt = 0; while(cin>>str) { if(str[0] == 'O') { cin>>xx; for(int i=0; i
>xx>>yy; int fx = Find(xx); int fy = Find(yy); if(fx == fy) puts("SUCCESS"); else puts("FAIL"); } } return 0;}

转载地址:http://ixpdx.baihongyu.com/

你可能感兴趣的文章
linux 启动oracle
查看>>
《写给大忙人看的java se 8》笔记
查看>>
倒计时:计算时间差
查看>>
Linux/windows P2V VMWare ESXi
查看>>
Windows XP倒计时到底意味着什么?
查看>>
tomcat一步步实现反向代理、负载均衡、内存复制
查看>>
运维工程师在干什么学些什么?【致菜鸟】
查看>>
Linux中iptables详解
查看>>
java中回调函数以及关于包装类的Demo
查看>>
maven异常:missing artifact jdk.tools:jar:1.6
查看>>
终端安全求生指南(五)-——日志管理
查看>>
Nginx 使用 openssl 的自签名证书
查看>>
创业维艰、守成不易
查看>>
PHP环境安装套件:快速安装LAMP环境
查看>>
CSS3
查看>>
ul下的li浮动,如何是ul有li的高度
查看>>
C++ primer plus
查看>>
python mysqlDB
查看>>
UVALive 3942 Remember the Word Tire+DP
查看>>
从微软的DBML文件中我们能学到什么(它告诉了我们什么是微软的重中之重)~目录...
查看>>