[swexpert] 1251. 하나로 (java, 크루스칼, union-find)

 

import java.util.PriorityQueue;
import java.util.Scanner;

class Bridge implements Comparable<Bridge>{
	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.dist<o.dist)return -1;
		else if(this.dist>o.dist)return 1;
		return 0;
	}
	
}

public class S_1251_하나로_Solution {
	static int t,n;
	static PriorityQueue<Bridge> bridge;
	static int[] xlist;
	static int[] ylist;
	static double answer,e;
	static int[] parent;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			answer=0;
			parent=new int[n+1];
			for (int i = 1; i <=n; i++) {
				parent[i]=i;
			}
			bridge=new PriorityQueue<>();
			xlist=new int[n];
			ylist=new int[n];
			for (int i = 0; i < n; i++) {
				xlist[i]=sc.nextInt();
			}

			for (int i = 0; i < n; i++) {
				ylist[i]=sc.nextInt();
			}

			e=sc.nextDouble();
			for (int i = 0; i < n; i++) {
				for (int j = i+1; j < n; j++) {
					int diffy=ylist[i]-ylist[j];
					int diffx=xlist[i]-xlist[j];
					double dis=Math.pow(diffy,2)+Math.pow(diffx, 2);
					bridge.add(new Bridge(i+1,j+1,dis));
				}
			}
			int len=bridge.size();
			for (int i = 0; i < len; i++) {
				Bridge cur=bridge.poll();
				union(cur.a,cur.b,cur.dist);
				
			}
			
			System.out.printf("#%d %.0f\n",tc,answer);
			
		}
		
	}


	private static int find(int x) {
		if(x==parent[x])return x;
		return parent[x]=find(parent[x]);	
	}
	private static void union(int a, int b, double dist) {
		a=find(a);
		b=find(b);
		if(a!=b) {
			answer+=e*dist;
			if(a<=b) {
				parent[b]=a;
			}else {
				parent[a]=b;
			}
		}
		
	}
}