Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 14086 | Accepted: 5962 |
Description
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
题意:
有N(1到1001)台机器和D最小距离(0到20000),给出每台机器的坐标(X,Y)(0到10000)。O代表已经修好某台机器,S代表询问A和B机器间是否能联系上。要能联系则必须两机器的坐标距离不大于D,如果A和B能连上,B和C能连上,那么A和C也能连上。输出当询问S时,两部机器能联系上的结果,能则输出SUCCESS,不能则输出FAIL。
思路:
普通并查集。但是与一般不同是它有一个距离的条件,并且每次输入O可能会更新一次连通集合。用rep数组来表示机器i是否已经修好,1为修好,0为没有修好。当输入O时,循环一次所有机器,当循环到有一台机器满足距离小于1,且这部机器已经是修好的,那就将该机器合并到该集合中。当输入S时,判断A和B的根节点是否相同则知道是否能连接上。
AC:
#include<stdio.h> #include<math.h> #include<string.h> typedef struct { int x; int y; }pos; pos num[1005]; int root[1005],rep[1005]; int n; double distance(pos a,pos b) { double s; s=sqrt(pow((double)a.x-(double)b.x,2)+pow((double)a.y-(double)b.y,2)); return s; } int find(int a) { int x=a,t; while(x!=root[x]) x=root[x]; while(x!=a) { t=root[a]; root[a]=x; a=t; } return x; } void merge(int a,int b) { int fa,fb; fa=find(a); fb=find(b); if(fa!=fb) root[fa]=fb; } int main() { int d; char c[5]; int a,b; scanf("%d%d",&n,&d); memset(rep,0,sizeof(rep)); for(int i=1;i<=n;i++) root[i]=i; for(int i=1;i<=n;i++) scanf("%d%d",&num[i].x,&num[i].y); while(scanf("%s",c)!=EOF) { if(c[0]=='O') { scanf("%d",&a); rep[a]=1; for(int i=1;i<=n;i++) if(distance(num[i],num[a])<=d&&rep[i]) merge(a,i); //这里的距离因为看了样例,然后固化了,写成小于1.0,然后又WA了N次 } else { scanf("%d%d",&a,&b); if(find(a)==find(b)) printf("SUCCESS\n"); else printf("FAIL\n"); //这里一开始写成FALL,WA了一次 } } return 0; }
总结:
1.一开始定义输入字符char c,输入的时候scanf(“%c”,&c)出现了错误,输入scanf(“% c”,&c)就不会出现错误了,也就是输入格式前面加个空格;
2.FAIL一开始打成FALL,低级错误;
3.距离是小于d不是小于样例给的1,又是低级错误;
4.一开始想的是:当O的时候登记rep为修好状态,当S的时候再一个个匹配合并,然后用了一个二重循环,先找到一个已经修好的,然后以这个修好的为基准再循环一层来找下一个修好的,然后匹配。这样无疑会TLE的。改进后就是每输入一次O就更新一次连通集合,没输入一次S就判断一次两者是否属于一个集合就可以了。
5.一开始还想过用一个二维数组来保存i到j是否能连上的状态,其实不需要,改进后只需要用个rep数组登记就好。
相关推荐
Designing a Wireless network <br>Foreword xxv <br>From Past to Present 1 <br>Introduction 2 <br>Exploring Past Discoveries That Led to Wireless 4 Discovering Electromagnetism 4 <br>...
killer网卡驱动,外星人笔记本,Wireless Network Adapter,1550,最新版本,9260NGW
wireless network coding. The results show that using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to ...
mac book osx 10.11 usb wifi 驱动 包含 Wireless Network Utility 中文版 mac book air 10.11实测可用
EEE802.11标准定义,主要安全措施,基于MAC地址鉴别机制
wireless sensor network综述
CWMA: Certified Wireless Network Administrator Study Guide
Wireless Network information Theory
Wireless Network Security and Interworking3,Wireless Network Security and Interworking3
wireless sensor network
是一个能扫描你的无线网络并显示连接到你的无线网络的计算机和设备的免费小工具Wireless Network Watcher is a small utility that scans your wireless network and displays the list of all computers and ...
wireless sensor network 教材
WireLess Network Watcher(局域网监视),有个挺好的轮巡算法,比我写的好用。
Wireless Network Watcher 用来扫描无线网络上的所有用户,并支持网卡选择。显示设备名称和MAC地址以及网络适配器名称等。 软件说明: 无线网络用户查看软件,一个体积小功能实用的绿色软件,小编为大家分享的是...
普联usb无线网卡驱动
Building Wireless Sensor Network
无线网络编码中的最大多流问题,周进怡,夏树涛,在多跳无线网络中,无线干扰是最大多流(MMF)问题的一个关键因素。最大多流问题关注一个网络中多对源、宿节点之间所能达到的最大��
With the increased demand for mobile connectivity and the decrease in cost and in the time required for installation, wireless network connections will make up 20% of all corporate network connections...
Description: Mobile and Wireless Network Security and Privacy analyzes important security and privacy problems in the realms of wireless networks and mobile computing. The material includes a report ...