https://www.acmicpc.net/problem/23034
23034번: 조별과제 멈춰!
교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각
www.acmicpc.net
1. 최소 신장 트리를 만듭니다.
2. X와 Y를 입력받으면, BFS를 이용하여 신장 트리에 사용된 간선 중 X에서 Y까지 가는 간선의 비용의 최댓값을 구합니다.
3. 최소 신장 트리의 비용에서 방금 구한 값을 뺍니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, M, Q, X, Y, cnt, sum;
static int[] parent;
static boolean[] visited;
static ArrayList<Line>[] lines, used;
static PriorityQueue<Line> pq = new PriorityQueue<>();
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
lines = new ArrayList[N + 1];
used = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
lines[i] = new ArrayList<>();
used[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
lines[from].add(new Line(from, to, cost));
lines[to].add(new Line(to, from, cost));
pq.add(new Line(from, to, cost));
}
make();
// MST 만들기
while(!pq.isEmpty()) {
Line l = pq.poll();
if(union(l.from, l.to)) {
used[l.from].add(l);
used[l.to].add(new Line(l.to, l.from, l.cost));
sum += l.cost;
if (++cnt == N - 1) break;
}
}
// 질문 처리
Q = Integer.parseInt(br.readLine());
for (int i = 0; i < Q; i++) {
st = new StringTokenizer(br.readLine(), " ");
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
sb.append(sum - bfs()).append("\n");
}
System.out.print(sb.toString());
}
static int bfs() {
visited = new boolean[N + 1];
Queue<Pos> q = new LinkedList<>();
visited[X] = true;
for (Line l : used[X]) {
q.offer(new Pos(l.to, l.cost));
}
while(!q.isEmpty()) {
Pos p = q.poll();
if(p.index == Y) return p.max;
for (Line l : used[p.index]) {
if(!visited[l.to]) {
visited[l.to] = true;
q.offer(new Pos(l.to, Math.max(p.max, l.cost)));
}
}
}
return 0;
}
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 Pos {
int index, max;
public Pos (int index, int max) {
this.index = index;
this.max = max;
}
}
static class Line implements Comparable<Line> {
int from, to, cost;
public Line (int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo (Line o) {
return this.cost - o.cost;
}
}
}
'OJ' 카테고리의 다른 글
[BOJ] 10988 팰린드롬인지 확인하기 (JAVA) (0) | 2023.01.30 |
---|---|
[BOJ] 11721 열 개씩 끊어 출력하기 (JAVA) (0) | 2023.01.29 |
[BOJ] 1620 나는야 포켓몬 마스터 이다솜 (JAVA) (0) | 2023.01.27 |
[BOJ] 4014 도로 (JAVA) (4) | 2023.01.26 |
[BOJ] 16950 레드 블루 스패닝 트리 2 (JAVA) (0) | 2023.01.25 |