[백준 12963] 달리기 (Platinum III)

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

 

 최대 유량의 정의를 알고 있다면, 이 문제는 최대 유량을 구하는 문제의 특수한 버전이라는 것을 쉽게 알 수 있다.

 그런데 최대 유량 최소 컷 정리에 의해 최대 유량의 값은 최소 컷의 값과 같다.

 간선의 value가 3^i 꼴로 주어지기 때문에, 최소 컷의 값을 그리디 알고리즘으로 구하기가 상당히 쉽다.

 최소 컷을 구하는 것은 가장 적은 비용의 간선을 자르는 것이므로, 가장 많은 비용의 간선을 살린다고 생각할 수도 있다. 그렇다면 가장 먼저 살려야 할 간선은 가장 value가 큰 간선임이 명백하다. 이는 value가 3^i 꼴로 주어지기 때문에 성립하는 것이고, 일반적인 상황에서는 성립하지 않는다.

 이 사실을 증명하는 것은 쉽다. 최종 결과를 3진수로 생각하면 된다. value가 가장 큰 간선을 죽이면, 나머지 간선을 모두 살리더라도 가장 큰 간선 하나만을 살리는 것보다 챙길 수 있는 value가 작다.

 따라서 가장 value가 큰 간선부터 살펴보며 살릴 수 있다면 그 간선을 무조건 살리고, 그렇지 않다면 눈물을 머금고 죽인다.

 언제 죽여야 할까? 우리는 최소 컷을 구하고 있으므로, 해당 간선을 살렸을 때 0번 정점과 n-1번 정점이 연결되면 죽여야 한다. 이것을 판별하는 것은 Disjoint set으로 가능하다.

 

 시간복잡도는 O(M)에 근접한다. Disjoint set 연산에 드는 시간복잡도인 아커만 함수는 너무 작으니 생략.

 

#ifndef ONLINE_JUDGE
#include "include/init.h"
#endif

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 P = 1000000007;

struct DJS {
    std::vector<int> parent;
    
    explicit DJS(int n) : parent(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int idx) {
        while (idx != parent[idx]) {
            idx = parent[idx] = parent[parent[idx]];
        }
        return idx;
    }
    
    void join(int l, int r) {
        int pl = find(l), pr = find(r);
        parent[pr] = pl;
    }
};

struct Edge {
    int l, r;
    i64 val;
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<Edge> edges(m);
    
    {
        i64 val = 1;
        for (auto& e : edges) {
            std::cin >> e.l >> e.r;
            e.val = val;
            val *= 3;
            val %= P;
        }
    }
    
    std::reverse(edges.begin(), edges.end());
    
    auto djs = DJS{n};
    i64 ret = 0;
    
    for (const auto& e : edges) {
        auto pl = djs.find(e.l);
        auto pr = djs.find(e.r);
        auto ps = djs.find(0);
        auto pe = djs.find(n - 1);
        if ((pl == ps && pr == pe) || (pl == pe && pr == ps)) {
            ret += e.val;
            ret %= P;
        } else {
            djs.join(e.l, e.r);
        }
    }
    
    std::cout << ret << '\n';
}

#ifdef ONLINE_JUDGE
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
}
#endif