OJ
[BOJ] 16202 MST 게임 (JAVA)
P3PP4
2023. 1. 12. 10:00
https://www.acmicpc.net/problem/16202
16202번: MST 게임
첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있
www.acmicpc.net
최소신장트리를 구하는 문제입니다.
그냥 Test Case마다 이전 Test Case에서의 최소 비용 간선을 하나씩 빼면 됩니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, M, K;
static int[] parent;
static ArrayList<Line> list = new ArrayList<>();
static Queue<Line> q = new LinkedList<>();
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken()); // 정점 수
M = Integer.parseInt(st.nextToken()); // 간선 수
K = Integer.parseInt(st.nextToken()); // 턴 수
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine(), " ");
list.add(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i));
}
t: for (int tc = 0; tc < K; tc++) {
make();
q.clear();
for (Line l : list) {
q.offer(l);
}
int cnt = 1;
int sum = 0;
int min = Integer.MAX_VALUE;
while(cnt < N) {
if(q.size() == 0) {
for (int i = tc; i < K; i++) {
sb.append(0).append(" ");
}
break t;
}
Line l = q.poll();
if(union(l.from, l.to)) {
cnt++;
sum += l.dist;
if(l.dist < min) min = l.dist;
}
}
sb.append(sum).append(" ");
for (int i = 0; i < list.size(); i++) {
if(list.get(i).dist == min) list.remove(i);
}
}
System.out.print(sb.toString());
}
static boolean union(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return false;
if(a < b) parent[b] = a;
else parent[a] = b;
return true;
}
static int find(int a) {
if(parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
static void make() {
parent = new int[N + 1];
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
}
static class Line {
int from, to, dist;
public Line(int from, int to, int dist) {
this.from = from;
this.to = to;
this.dist = dist;
}
}
}