중량제한

https://www.acmicpc.net/problem/1939

풀이

중량 제한이 있고 진행하는 경로 상에서는 가장 작은 중량 제한을 가지는 간선을 선택해야 하고 경로를 결정하는 것에는 중량 제한이 큰 간선들을 선택해야 한다.

그러기 위해 MST를 변형한 최대 신장 트리를 이용해서 풀이한다.

최소 신장 트리는 비용이 작은 간선부터 선택을 하여 트리를 만든다면 최대 신장 트리는 비용이 큰 간선부터 선택을 하여 트리를 만든다.

이렇게 하면 앞서 생각했던 내용들을 구현할 수 있다. 비용이 큰 경로만을 선택하여 만들어진 경로이고 이 때 가장 작은 비용이 문제의 답이 된다.

코드

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

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static PriorityQueue<Edge> priorityQueue;
    static int[] p;
    static int[] rank;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        priorityQueue = new PriorityQueue<>();
        p = new int[n + 1];
        rank = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            p[i] = i;
            rank[i] = 1;
        }

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            priorityQueue.add(new Edge(x, y, w));
            //bw.write(count + "\n");
        }
        String[] last = br.readLine().split(" ");
        int src = Integer.parseInt(last[0]);
        int dest = Integer.parseInt(last[1]);
        int ans = mst(src, dest);
        bw.write(ans + "\n");
        bw.close();
        br.close();
    }

    private static int mst(int src, int dest) {
        while (!priorityQueue.isEmpty()) {
            Edge e = priorityQueue.poll();
            int x = e.x;
            int y = e.y;
            union(x, y);
            if (find(src) == find(dest))
                return e.w;
        }
        return -1;
    }

    private static int union(int a, int b) {
        int ar = find(a);
        int br = find(b);

        if (ar != br) {
            if (rank[ar] < rank[br])
                p[ar] = br;
            else {
                p[br] = ar;
                if (rank[ar] == rank[br]) {
                    rank[ar]++;
                }
            }
        }
        return rank[ar];
    }

    private static int find(int a) {
        if (a == p[a])
            return a;
        else {
            int y = find(p[a]);
            p[a] = y;
            return y;
        }
    }
}

class Edge implements Comparable<Edge> {
    public int x;
    public int y;
    public int w;

    public Edge(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(o.w, this.w);
    }
}

추가

추가로 이분탐색+bfs로 풀이할 수 있는데 이 방법은 추후 정리해서 추가할 예정이다.