POJ 2236 Wireless Network
Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 16131 | Accepted: 6801 |
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
Source
哇 ,自己做并查集,一次ac。。
#include <iostream> #include <cstring> #define maxn 1005 using namespace std; struct point { int mast; int x,y; }f[maxn]; int find(int x) { if(f[x].mast==x) return x; else return (f[x].mast=find(f[x].mast)); } int main() { int n,d; cin>>n>>d; int i; for(i=1;i<=n;i++) { cin>>f[i].x>>f[i].y; f[i].mast=i; } char s; bool pd[maxn]; memset(pd,0,sizeof(pd)); while(cin>>s) { if(s=='S') { int x,y; cin>>x>>y; if(find(x)==find(y)) cout<<"SUCCESS"<<endl; else cout<<"FAIL"<<endl; } if(s=='O') { int x; cin>>x; pd[x]=1; for(i=1;i<=n;i++) { if(pd[i]==1&&i!=x) { if((f[i].x-f[x].x)*(f[i].x-f[x].x)+(f[i].y-f[x].y)*(f[i].y-f[x].y)<=d*d) { int a,b; a=find(i); b=find(x); if(a!=b) f[a].mast=b; } } } } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。