Wireless Network -- 검색 집합
3949 단어 데이터 구조
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
The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:
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
For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" if not.
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
분석: 이 문 제 는 하나의 집합 을 찾 는 간단 한 응용 이다. 문제 가 주 는 거리 치 를 만족 시 키 면 연결 할 수 있 는 집합 에 포함 시 킬 수 있 고 수 리 된 조건 도 만족 시 켜 야 한다. 만약 에 두 컴퓨터 가 모두 이 집합 안에 있다 면 통신 할 수 있다.
상위 코드:
import java.util.*;
public class Main {
static Scanner in = new Scanner(System.in);
static int n,d;
static boolean[] vis = new boolean[1005];
static int[] f = new int[1005];
static List st = new ArrayList();
//
static double dis(Node s1,Node s2){
double d=Math.sqrt((s1.x-s2.x)*(s1.x-s2.x)+(s1.y-s2.y)*(s1.y-s2.y));
return d;
}
//
static void judge(int x){
for (int i = 1; i <= n; i++) {
//
if(vis[i]&&dis(st.get(i-1),st.get(x-1))<=d+(1e-6))
merge(i, i+1);
}
}
static int find(int x){
int r = x;
while(r!=f[r]){
r=f[r];
}
return r;
}
static void merge(int x,int y){
int t1 = find(x);
int t2 = find(y);
if(t1!=t2)
f[t1]=t2;
}
public static void main(String[] args) {
Arrays.fill(vis, false);
n = in.nextInt();
d = in.nextInt();
for (int i = 1; i <=n; i++) {
f[i]=i;
}
for (int i = 1; i <= n; i++) {
Node s = new Node();
s.x=in.nextInt();
s.y=in.nextInt();
st.add(s);
}
String s;
int t1,t2;
while(in.hasNext()){
s = in.next();
if(s.charAt(0)=='0'){
t1 = in.nextInt();
vis[t1]=true;// , 。。
judge(t1);
}else{
t1 = in.nextInt();
t2 = in.nextInt();
if(find(t1)==find(t2))// ,
System.out.println("SUCCESS");
else
System.out.println("FAIL");
}
}
}
}
class Node{
int x,y;
}
판단 조건 이 끊임없이 합병 되 는 것 은 실질 적 으로 하나 이다.
합병 할 때 제약 조건 이 있 는 집합...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.