SW expert 3124 최소 스패닝 트리 (자바)

SW expert 3124 최소 스패닝 트리 (자바)

728x90

import java.util.Arrays; import java.util.Scanner; import java.io.FileInputStream; class Solution { public static void main(String args[]) throws Exception { System.setIn(new FileInputStream("sample_input.txt")); Scanner sc = new Scanner(System.in); int T; T=sc.nextInt(); for(int test_case = 1; test_case <= T; test_case++) { long answer = 0; int V = sc.nextInt(); int E = sc.nextInt(); int[] parents = new int[V+1]; Line[] lines = new Line[E]; for (int i = 0; i < E; i++) { lines[i] = new Line(sc.nextInt(), sc.nextInt(), sc.nextInt()); } for (int i = 1; i <= V; i++) { parents[i] = i; } Arrays.sort(lines); int count=0; for (Line line : lines) { int a = findParent(parents,line.a); int b = findParent(parents,line.b); if(a!=b) { unionParent(parents,a,b); count++; answer+=line.cost; } if(count==V-1) break; } System.out.printf("#%d %d

",test_case,answer); } } private static void unionParent(int[] parents, int a, int b) { if(a{ int a; int b; int cost; public Line(int a, int b, int cost) { super(); this.a = a; this.b = b; this.cost = cost; } @Override public int compareTo(Line o) { // TODO Auto-generated method stub return this.cost - o.cost; } }

728x90

from http://arch1tect.tistory.com/152 by ccl(A) rewrite - 2021-09-16 13:27:13