POJ 2236 Wireless Network 几何+并查集
Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 14794 | Accepted: 6227 |
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
//4340K 3079MS #include<stdio.h> #include<string.h> #include<math.h> #define M 1007 char s[5]; int x[M],y[M],pre[M],vis[M],g[M][M]; int n,d; void init() { memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) { pre[i]=i; vis[i]=0; } } int find(int x) { while(x!=pre[x]) x=pre[x]; return x; } bool judge(int i,int j) { return ((y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i]))<=d*d; } int main() { scanf("%d%d",&n,&d); init(); int a,b,c; for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]); while(scanf("%s",s)!=EOF) { if(s[0]==‘O‘) { scanf("%d",&c); vis[c]=1; for(int i=1;i<=n;i++) { if(i==c)continue; if(judge(c,i)&&vis[i]) { int xx=find(c); int yy=find(i); pre[xx]=yy; } } } if(s[0]==‘S‘) { scanf("%d%d",&a,&b); if(find(a)==find(b))printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。