import java.util.PriorityQueue; import java.util.Scanner; class Bridge implements Comparable { int a; int b; double dist; public Bridge(int a,int b, double dist) { super(); this.a=a; this.b=b; this.dist = dist; } @Override public int compareTo(Bridge o) { if(this.disto.dist)return 1; return 0; } } public class S_1251_하나로_Solution { static int t,n; static PriorityQueue bridge; static int[] xlist;..
scanner로 입력받으면 시간 초과한다. union으로 합칠 때 트리 깊이가 더 작은 것을 더 큰 것에 붙여줘야한다. 안 그러면 시간 초과난다. (다른 애들을 검사할 때 깊이가 점점 더 깊어지기 때문에) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.StringTokenizer; // 정올 1863 종료 public class Main { static int n,m; static int[] parent; static int[] depth; public static ..
먼저 union-find 알고리즘으로 그룹을 연결해준다. vis배열 (해당 집합 그룹을 방문했는지)를 만든 다음 1번부터 n번까지 체크해준다. 이미 앞에서 방문한 집합에 속한 번호라면 pass 방문했던 집합에 속하지 않은 번호라면 1. 먼저 친구비를 내서 사귈 수 있는 친구인지 확인한다. 2. 해당 번호가 속한 집합의 vis를 true로 해주고 방문한 번호의 개수(cnt)를 1 증가시킨다. 3. 낸 비용만큼 answer를 증가시킨다. import java.util.Scanner; //친구비 public class B_16562_Main { static int n,m,k; static int[] money; public static void main(String[] args) { Scanner sc=new..