poj-2236 wireless network(并查集)
2018-12-04 07:13:27来源:博客园 阅读 ()
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
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
Sample Input
4 1 0 1 0 2 0 3 0 4 O 1 O 2 O 4 S 1 4 O 3 S 1 4
Sample Output
FAIL SUCCESS
题目大意:修复和测试,然后输出结果
题解:并查集的模版题,直接看代码吧
#include<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<cstdlib> #include<queue> using namespace std; #define PI 3.14159265358979323846264338327950 int father[20010],num; int p[20010]={0},n; struct point { double x; double y; }pt[1005]; int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0); } void combine(int a,int b) { int fa=find(a); int fb=find(b); if(fa!=fb) father[fa]=fb; } int main() { int i,x,y; double d; char control[2]; scanf("%d %lf",&n,&d); for(int i=0;i<1005;i++) father[i]=i; for(int i=1;i<=n;i++) { scanf("%lf %lf",&pt[i].x,&pt[i].y); } while(scanf("%s",control)!=EOF) { if(control[0]=='O') { scanf("%d",&x); p[x]=1; for(i=1;i<=n;i++) { if(dis(pt[i],pt[x])<=d&&p[i]==1) combine(i,x); } } if(control[0]=='S') { scanf("%d%d",&x,&y); if(find(x)==find(y)) printf("SUCCESS\n"); else printf("FAIL\n"); } } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ3732: Network(Kruskal重构树) 2018-07-22
- 概述「DAG加边至强连通」模型&&luoguP2746 2018-07-09
- uva 1590 - IP Networks(IP地址) 2018-06-18
- FSLIB.NETWORK 简易使用指南 2018-06-18
- POJ 2236 Wireless Network 第一次做并查集,第一次写博客 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash