Boj 13418

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

13418번: 학교 탐방하기

 

문제를 이해하는데 한참 걸렸다.

그냥 MST(크루스칼)로 푸는 문제인데..

 

단 예외 조건이 있다, 오르막이 0, 내리막이 1로 제공된다.

따라서, 1-C (0->1 / 1->0)  으로 적용해야 한다.

또한 "입력받은 데이터에 대해, 주어진 조건을 만족하는 최악의 경로에서의 피로도와 최적의 경로 간 피로도의 차이를 출력한다." 라고 한다.

아래 문구가 젤 중요하다.

오르막길을 k번 오를 때, 피로도는 k2이 된다. 피로도의 계산은 최초 조사된 길을 기준으로만 한다. 즉, 내리막길로 내려갔다 다시 올라올 때 오르막길이 되는 경우는 고려하지 않는다

 

암튼 문제가 푸는게 어려운게 아니라, 문제를 이해하는게 어렵다.

 

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class boj13418 {
    static int N, M;
    static DJS djs;
    static Node[] nodes;
    static class Node {
        int s, e, v;
        Node(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }
    static class DJS {
        int[] mom;
        DJS(int n) {
            mom = new int[n+1];
            for (int i = 1; i <= n; i++) mom[i] = i;
        }
        int find(int n) {
            return (n==mom[n])? n : (mom[n] = find(mom[n]));
        }

        boolean union(int a, int b) {
            a = find(a);
            b = find(b);
            if(a==b) return false;
            mom[b] = a;
            return true;
        }
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj13418.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        djs = new DJS(N);
        nodes = new Node[M+1];

        int a, b ,c;
        for (int i = 0; i < M+1 ; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            nodes[i] = new Node(a, b, 1-c);
        }

        // Kruskal
        Comparator<Node> cmp = (o1, o2) -> o1.v - o2.v;
        Arrays.sort(nodes, cmp);

        long max = 0;
        long min = 0;
        for (int i = 0; i < M+1 ; i++) {
            if(djs.union(nodes[i].s, nodes[i].e)) {
                min += nodes[i].v;
            }
        }

        cmp = (o1,o2) -> o2.v - o1.v;
        Arrays.sort(nodes, cmp);
        djs = new DJS(N);
        for (int i = 0; i < M+1 ; i++) {
            if(djs.union(nodes[i].s, nodes[i].e)) {
                max += nodes[i].v;
            }
        }

        System.out.println((max*max) - (min*min));
    }
}