문제

아이디어

합산 가중치가 가장 작도록 집들을 두 마을로 묶으면 되는 최소 스패닝 트리 문제이다.
우선 크루스칼 알고리즘을 통해 최소 스패닝 트리를 구한 후, 가장 코스트가 높은 길 하나를 제거한다면 가중치가 가장 작은 두 마을을 구할 수 있다.
초기 상황에서 임의의 두 집 사이에 경로가 항상 존재함이 보장되므로, 별도의 예외 처리를 해주지 않아도 괜찮다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static int[] parent;
    static int ans;
    static StringTokenizer st;
    static PriorityQueue<Edge> pq;

    static class Edge implements Comparable<Edge> {
        int v;
        int u;
        int weight;

        public Edge(int v, int u, int weight) {
            this.v = v;
            this.u = u;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return false;

        if (x <= y) parent[y] = x;
        else parent[x] = y;
        return true;
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        parent = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            parent[i] = i;
        }
        pq = new PriorityQueue<>();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            pq.add(new Edge(v, u, weight));
        }

        int max = -1;
        while (!pq.isEmpty()) {
            Edge e = pq.poll();

            if (union(e.v, e.u)) {
                ans += e.weight;
                max = Math.max(max, e.weight);
            }
        }

        System.out.println(ans - max);
    }
}

채점 결과

최소 스패닝 트리의 간단한 응용이었다.