BOJ 12963

문제의 핵심 관찰은 3^n보다 작은 3의 제곱수들을 아무리 더해도 3^n을 넘을 수 없다는 것이다. 즉, 시작점에서 끝점으로 가는 경로에서 가장 작은 용량을 갖는 간선만 파악한다면 나머지 간선들은 신경쓸 필요가 없다. 그래프의 간선의 가중치가 이런식으로 제곱수의 형태를 갖는 경우, 대개 a^0 + ... + a^n - 1 < a^n인 특성을 이용하는 문제가 많은 것 같다.

 

입력된 간선들을 역순으로 뒤집고 3의 제곱수들의 나머지를 미리 계산해 놓은 다음, Union Find로 0과 n - 1이 합쳐지는 순간 가장 작은 용량을 정답에 더하면 된다. 이때, 합쳐지는 순간 가장 작은 용량을 갖는 간선은 포화상태가 되기 때문에 없는 것과 마찬가지이다. Union을 수행하기 이전의 배열을 저장해 두었다가 0과 n - 1이 합쳐졌다면 정답에 값만 더해 주고 배열은 원래대로 되돌리면 된다.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

constexpr ll MOD = 1e9 + 7;

inline void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

vector<ll> p;

ll find(ll x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

int main() {
    init();

    ll n, m;

    cin >> n >> m;

    vector<pll> edges(m);
    vector<ll> sz(1, 1LL);
    p.resize(n);

    for (auto& [u, v] : edges) {
        cin >> u >> v;
        sz.emplace_back(sz.back() * 3 % MOD);
    }

    iota(p.begin(), p.end(), 0LL);
    ll ans = 0;

    for (ll i = m - 1; i >= 0; i--) {
        auto [u, v] = edges[i];
        u = find(u), v = find(v);

        if (u != v) {
            auto tmp = p;
            p[u] = v;

            if (find(0) == find(n - 1)) {
                ans = (ans + sz[i]) % MOD;
                p = tmp;
            }
        }
    }

    cout << ans;

    return 0;
}