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

문제: icpc.me/1626

두 번째로 작은 스패닝 트리를 구하는 문제이다.

우선 정점이 V개 간선이 E개인 그래프에서 MST를 구해준다.

그리고 MST를 구성할 때 사용하지 않은 E-V+1개의 간선에 대해서 해당 간선을 포함하는 MST를 구하여 답을 구해낸다..

하지만 E-V+1번 크루스칼을 돌린다면 TLE를 보게 될것이다.

그렇다면 E-V+1개의 간선을 각각 포함하는 MST를 어떻게 구해낼 수 있을까?

우선 현재 보고 있는 간선이 1번 정점과 5번 정점을 연결한다고 가정해보자.

그렇다면 우리는 기존의 MST에서 1번 정점과 5번 정점을 연결해주어 N개의 간선을 가진 그래프를 생각해보자.

해당 그래프를 트리로 만드려면 하나의 간선을 제거해야한다. 이 때 제거되야 되는 간선은 1번 정점과 5번 정점을 연결하는 경로에 있는 간선들 중 하나일 것이다.

따라서 우리는 E-V+1개의 간선들에 대해서 기존 MST값 + 해당 간선의 값 - V1정점에서 V2정점으로의 경로에 있는 간선의 값중 최댓값들을 구해주면 된다.

하지만 V1 정점에서 V2 정점으로의 경로 중 최댓값을 선형으로 탐색할 경우 최악의 경우 O(V)의 시간복잡도를 가지게 된다.

이렇게 구하게 될 경우 역시 TLE를 보게된다.

따라서 우리는 V1 정점에서 V2 정점으로의 경로 중 최댓값을 빠르게 구해내야하는데 

MST에서의 경로이므로 트리라는 조건이기 때문에 LCA를 이용하여 가능하다. 

LCA를 구하기 위한 2^N번째 부모를 저장할 때 2^N번째 간선까지의 최댓값을 같이 저장하여 준다면 O(logV)시간에 경로의 최댓값을 구해낼 수 있다.

이제 답을 구할 수 있겠다고 생각 되겠지만 안타깝게도 또 처리해주어야 하는 부분이 존재한다...

예를들어 아까의 경우 1번 정점과 5번 정점을 잇는 간선의 가중치가 8이라고 해보자.

그리고 LCA를 이용하여 얻어낸 간선의 경로 중 최댓값이 8이라고 한다면 우리는 기존 MST와 똑같은 값을 답으로 구해낼 것이다.

하지만 이 경우는 답이되면 안되기 때문에 이런 경우를 차단해주어야 한다.

그렇다면 LCA를 구하는 도중에 간선의 가중치가 내가 현재 보는 간선의 가중치와 같을 경우에 그 경로의 간선들을 또 탐색해내어야 하는데

이걸 또 선형으로 구한다면 TLE를 보게 될테니 이진 탐색을 이용하여서 구해내어야 한다.

조금 복잡하니 소스코드로 확인하도록 하자.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int v, e, p[50050], c[200020], par[50050][22], g[50050][22], h[50050], x, y, z, f, cnt;
vector<pair<int, pair<int, int>>> vt;
vector<vector<pair<int, int>>> mst;
int find(int h){
    return h == p[h] ? h : p[h] = find(p[h]);
}
bool merge(int x, int y, int z) {
    if (find(x) == find(y))return false;
    mst[x].push_back({ y ,z });
    mst[y].push_back({ x ,z });
    f += z;
    p[find(x)] = find(y);
    return true;
}
void dfs(int curr, int prev) {
    for (auto next : mst[curr]) {
        if (next.first == prev)continue;
        h[next.first] = h[curr] + 1;
        par[next.first][0] = curr;
        g[next.first][0] = next.second;
        dfs(next.first, curr);
    }
}
int bsch(int x, int y, int z) {
    if (y == 0)return 0;
    int ret = 0;
    if (g[x][y - 1] == z) 
        ret = max(ret, bsch(x, y - 1, z));
    else
        ret = max(ret, g[x][y - 1]);
    if (g[par[x][y - 1]][y - 1] == z)
        ret = max(ret, bsch(par[x][y - 1], y - 1, z));
    else
        ret = max(ret, g[par[x][y - 1]][y - 1]);
    return ret;
}
int getmax(int x, int y, int z) {
    if (h[x] > h[y])
        swap(x, y);
    int ret = 0;
    for (int i = 20; i >= 0; i--) {
        if ((h[y] - h[x]) >= (1 << i)) {
            if (g[y][i] == z)
                ret = max(ret, bsch(y, i, z));
            else
                ret = max(ret, g[y][i]);
            y = par[y][i];
        }
    }
    if (x == y)return ret;
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            if (g[x][i] == z)
                ret = max(ret, bsch(x, i, z));
            else
                ret = max(ret, g[x][i]);
            if (g[y][i] == z)
                ret = max(ret, bsch(y, i, z));
            else
                ret = max(ret, g[y][i]);
            x = par[x][i];
            y = par[y][i];
        }
    }
    if (g[x][0] != z)
        ret = max(ret, g[x][0]);
    if (g[y][0] != z)
        ret = max(ret, g[y][0]);
    return ret;
}
int main() {
    scanf("%d%d", &v, &e);
    mst.resize(v + 1);
    for (int i = 1; i <= v; i++)
        p[i] = i;
    for (int i = 0; i < e; i++) {
        scanf("%d%d%d", &x, &y, &z);
        vt.push_back({ z,{x,y} });
    }
    sort(vt.begin(), vt.end());
    for (int i = 0; i < e; i++) {
        if (merge(vt[i].second.first, vt[i].second.second, vt[i].first)) {
            c[i]++;
            cnt++;
        }
        if (cnt == v - 1)
            break;
    }
    if (cnt != v - 1 || e <= v - 1) {
        puts("-1");
        return 0;
    }
    dfs(1, 0);
    for (int j = 1; j < 21; j++) {
        for (int i = 1; i <= v; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            g[i][j] = max(g[par[i][j - 1]][j - 1], g[i][j - 1]);
        }
    }
    ll r = 1e11;
    for (int i = 0; i < e; i++) {
        if (c[i])continue;
        int gmax = getmax(vt[i].second.first, vt[i].second.second, vt[i].first);
        if (!gmax)continue;
        r = min(r, (ll)(f - gmax + vt[i].first));
    }
    if (r == 1e11 || r == f)puts("-1");
    else
        printf("%lld\n", r);
    return 0;
}