27498 백준 연애 혁명

풀이

이미 성사된 사랑 관계라면 같은 집합으로 묶어준다.

이루어지지 않은 관계들끼리 애정도(가중치)를 기준으로 내림차순하고 최소 스패닝 트리(MST)를 구성한다.

최소 스패닝 트리에 포함되지 않은 관계들의 총합이 정답이 된다.

이루어지지 않은 관계들의 애정도의 합을 먼저 구하고 최소 스패닝 트리에 포함된 관계들의 애정도의 총합을 뺀 것이 포기하도록 만든 애정도의 총합이 된다.

코드

package test27498;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int[] parent;
	static int N; // 학생의 수
	static int M; // 사랑 관계의 수

	static int[][] edges; // edge 입력

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		
		int result = 0;

			M = sc.nextInt();
			N = sc.nextInt();
			parent = new int[N + 1];
			for (int i = 1; i <= N; i++) {
				parent[i] = i;
			}

			edges = new int[N][4];

			int total_cost = 0;
			for (int i = 0; i < N; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				int z = sc.nextInt();
				int a = sc.nextInt();
				if(a == 0) {
					edges[i][0] = x;
					edges[i][1] = y;
					edges[i][2] = z;
					edges[i][3] = a; 
				total_cost += edges[i][2];
				} else {
					union(x, y);
				}
			}

			Arrays.sort(edges, (a, b) -> b[2] - a[2]); // 간선을 기준으로 내림차순으로 정렬
			
			int min_cost = 0;
			for (int i = 0; i < edges.length; i++) {
		        int Start = edges[i][0];
		        int End = edges[i][1];
		        int Cost = edges[i][2];
		        if (find(Start) != find(End)) {
		        	union(Start, End);
		        	min_cost += Cost;
		        }
		    }
			System.out.println(total_cost - min_cost);;
	}

	public static int find(int idx) {
		if (parent[idx] == idx) {
			return idx;
		}
		parent[idx] = find(parent[idx]);
		return parent[idx];
	}

	public static void union(int a, int b) {
		int parent_of_a = find(a);
	    int parent_of_b = find(b);
	    if (parent_of_a < parent_of_b) {
	    	parent[parent_of_b] = parent_of_a;
	    }
	    else {
	    	parent[parent_of_a] = parent_of_b;
	    }
	}
	
	

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}

	}
}

참고

크루스칼 알고리즘

union-find