1626번: 두 번째로 작은 스패닝 트리

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

MST를 이루는 간선(e1)을 하나 제거하고 그 간선과 다른 가중치의 간선(e2)으로 forest를 연결해보자. 두 번째로 작은 스패닝 트리는 (e2의 가중치) - (e1의 가중치)가 가장 작을 때 만들어 진다.

e2를 MST에 추가하면 그래프에는 정확히 하나의 사이클이 존재하고 그 사이클에 e1과 e2가 모두 존재한다. 다시 말해 MST에서 e2의 양 끝 정점을 연결하는 MST 위의 경로 중에 e1이 존재한다.

(e2의 가중치) - (e1의 가중치)의 최솟값을 구하기 위해선 MST에 없는 간선(e2)마다 트리 위의 경로 중 가중치가 해당 간선보다 작으면서 가장 큰 간선(e1)을 찾으면 된다.

이러한 문제는 LCA를 구해서 해결할 수 있는 문제로 기본적인 트릭이 잘 알려져 있다. 아래 소스에서는 sparse table을 이용하여 주어진 두 정점에 대해 LCA 및 1, 2번째 최소 가중치 간선을 $O(\lg n)$에 구할 수 있도록 구현했다. 여기서 두 개의 최소 가중치를 구하는 이유는 만약 첫 번째 최소 가중치가 e2의 가중치와 같을 경우 두 번째 가중치를 사용해야 하기 때문이다.

답은 (MST 가중치) + min( (e2의 가중치) - (e1의 가중치) )이다.

최종 시간복잡도는 $O(e\lg v)$

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct edge {
    int x, y, d;
}ed[200000];
struct st {
    int f = -1, s = -1;
    st operator+(st t) const {
        st ret = *this;
        if (ret.f^t.f) ret.s = max(ret.s, t.f);
        if (ret.f < ret.s) swap(ret.f, ret.s);
        ret.s = max(ret.s, t.s);
        return ret;
    }
}maxi[50001][16];
int v, e, par[50001], tot, dp[50001][16], lv[50001], ck[200000], cnt, res = -1;
vector<pair<int, int> > adj[50001];
int p(int x) { return x^par[x] ? par[x] = p(par[x]) : x; }
void f(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) {
        dp[it.first][0] = h;
        maxi[it.first][0].f = it.second;
        for (int i = 1; i < 16; i++) {
            dp[it.first][i] = dp[dp[it.first][i - 1]][i - 1];
            maxi[it.first][i] = maxi[dp[it.first][i - 1]][i - 1] + maxi[it.first][i - 1];
        }
        lv[it.first] = lv[h] + 1;
        f(it.first, h);
    }
}
st query(int x, int y) {
    st ret;
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = 16; i--;) if (1 << i <= lv[x] - lv[y]) ret = ret + maxi[x][i], x = dp[x][i];
    if (x == y) return ret;
    for (int i = 16; i--;) if (dp[x][i] != dp[y][i]) {
        ret = ret + maxi[x][i] + maxi[y][i];
        x = dp[x][i];
        y = dp[y][i];
    }
    return ret + maxi[x][0] + maxi[y][0];
}
int main() {
    scanf("%d%d", &v, &e);
    for (int i = 0; i < e; i++) scanf("%d%d%d", &ed[i].x, &ed[i].y, &ed[i].d);
    sort(ed, ed + e, [](edge i, edge j) {return i.d < j.d; });
    for (int i = 1; i <= v; i++) par[i] = i;
    for (int i = 0; i < e; i++) {
        int ra = p(ed[i].x), rb = p(ed[i].y);
        if (ra^rb) {
            par[ra] = rb;
            adj[ed[i].x].push_back({ ed[i].y,ed[i].d });
            adj[ed[i].y].push_back({ ed[i].x,ed[i].d });
            tot += ed[i].d;
            ck[i] = 1;
            cnt++;
        }
    }
    if (cnt^v - 1) { puts("-1"); return 0; }
    f(1, 0);
    for (int i = 0; i < e; i++) if (!ck[i]) {
        st ret = query(ed[i].x, ed[i].y);
        if (ret.f^ed[i].d && (!~res || res>ed[i].d - ret.f + tot)) res = ed[i].d - ret.f + tot;
        if (~ret.s && (!~res || res>ed[i].d - ret.s + tot)) res = ed[i].d - ret.s + tot;
    }
    printf("%d", res);
    return 0;
}