POJ 2236Wireless Network
题目来源:http://poj.org/problem?id=2236
Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 16470 | Accepted: 6942 |
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<cstdio> #include<cmath> const int Max=1002; struct Node{ double x,y;int loc; }father[Max]; int set[Max],pos=0,n,dx,dy; char ch; double d; bool dis(int x,int k){ double di=sqrt(pow(father[x].x-father[k].x,2)+pow(father[x].y-father[k].y,2)); if(di<=d) return true; return false; } int find(int k){ if(k==father[k].loc) return k; int temp=find(father[k].loc); father[k].loc=temp; return temp; // return find(father[k].loc); } int main(){ scanf("%d%lf",&n,&d); for(int i=1;i<=n;i++){ scanf("%lf%lf",&father[i].x,&father[i].y); father[i].loc=i; } while(getchar(),~scanf("%c",&ch)){ if(ch=='O'){ scanf("%d",&dx); for(int i=0;i<pos;i++){ if(dis(dx,set[i])){ int tempx=find(set[i]); father[tempx].loc=find(dx); } } set[pos++]=dx; } else { scanf("%d%d",&dx,&dy); int tempx=find(dx),tempy=find(dy); if(tempx==tempy) printf("SUCCESS\n"); else printf("FAIL\n"); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。