[백준 1626] 두 번째로 작은 스패닝 트리

문제

www.acmicpc.net/problem/1626

 

알고리즘

hld, mst

 

풀이

MST 대신 두 번째로 작은 스패닝 트리를 구하는 문제입니다.

 

접근은 그리디하게 MST에서 가장 큰 간선을 제거하는 것입니다. MST를 만들 때 사용하지 않은 간선들을 검사하며 이 때 간선의 양 끝 정점을 $u, v$라고 합시다. MST를 구성했다면 $u, v$를 잇는 경로는 무조건 존재하게 됩니다. $u, v$를 연결하는 경로에서 가장 큰 간선을 제거하고 현재 사용하지 않은 간선으로 대체하며 풀어나가면 됩니다.

 

현재 사용하지 않은 간선의 무게와 $u, v$를 잇는 가장 큰 간선의 무게가 같은 경우가 있습니다. 이 경우는 MST가 유일하지 않은 경우입니다. 문제에서는 MST와 second  MST를 다른 값으로 구분하고 있으므로 가장 큰 간선 뿐만 아니라 두 번째로 큰 간선 또한 구해서 다른 MST를 구했다면 답으로 처리하지 않아야 합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

#define int long long
#define left (i << 1)
#define right (i << 1 | 1)

struct edge {
    int u, v, w;
};

typedef pair<int, int> pii;

const int MAXE = 2e5;
const int MAXV = 5e4;

int V, E, cnt, len;

edge edges[MAXE];
bool used[MAXE];
int par[MAXV];
int top[MAXV], pa[MAXV], sz[MAXV], idx[MAXV];

vector<vector<int>> adj;
vector<pii> tree;

pii pMax(pii a, pii b) {
    auto [af, as] = a;
    auto [bf, bs] = b;
    if (af == bf)
        return { af, max(as, bs) };
    return { max(af, bf), max(min(af, bf), max(as, bs)) };
}

int dfs(int here) {
    sz[here] = 1;
    for (auto& there : adj[here]) {
        if (pa[here] ^ there) {
            pa[there] = here;
            sz[here] += dfs(there);
            int& h = adj[here][0];

            if (h == pa[here] || sz[h] < sz[there])
                swap(h, there);
        }
    }
    return sz[here];
}

void hld(int here) {
    idx[here] = cnt++;
    for (auto there : adj[here]) {
        if (there ^ pa[here]) {
            top[there] = there == adj[here][0] ? top[here] : there;
            hld(there);
        }
    }
}

void init() {
    rep(i, E) {
        if (used[i]) {
            auto& [u, v, w] = edges[i];
            if (pa[u] == v)
                swap(u, v);
            tree[len + idx[v]].first = w;
            tree[len + idx[v]].second = -1;
        }
    }
    for (int i = len - 1; i > 0; --i) {
        tree[i] = pMax(tree[left], tree[right]);
    }
}

int find(int x) {
    return (par[x] < 0) ? x : (par[x] = find(par[x]));
}

pii query1(int l, int r) {
    l += len;
    r += len;

    pii ret = { -1, -1 };

    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) {
            ret = pMax(ret, tree[l++]);
        }
        if (!(r & 1)) {
            ret = pMax(ret, tree[r--]);
        }
    }
    return ret;
}

pii solve(int u, int v) {
    pii ret = { -1, -1 };
    while (top[u] ^ top[v]) {
        if (sz[top[u]] < sz[top[v]])
            swap(u, v);
        ret = pMax(ret, query1(idx[top[v]], idx[v]));
        v = pa[top[v]];
    }
    if (idx[u] > idx[v])
        swap(u, v);
    ret = pMax(ret, query1(idx[u] + 1, idx[v]));
    return ret;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> V >> E;
    len = pow(2, ceil(log2(V)));
    tree.resize(len << 1, { -1, -1 });
    adj.resize(V);
    rep(i, E) {
        auto& [u, v, w] = edges[i];
        cin >> u >> v >> w;
        --u, --v;
    }

    memset(par, -1, sizeof(par));
    sort(edges, edges + E, [](auto& a, auto& b) { return a.w < b.w; });

    int ans = 0;
    int CNT = 0;
    rep(i, E) {
        auto [u, v, w] = edges[i];
        int a = find(u);
        int b = find(v);

        if (a ^ b) {
            used[i] = true;
            ++CNT;
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);

            par[a] = b;
            ans += w;
        }
    }
    if (CNT != V - 1) {
        cout << -1;
        return 0;
    }
    dfs(0);
    hld(0);
    init();

    int ret = LLONG_MAX;

    rep(i, E) {
        if (!used[i]) {
            auto [u, v, w] = edges[i];

            auto [fir, sec] = solve(u, v);

            if (fir != -1 && fir != w) {
                ret = min(ret, ans - fir + w);
            } else if (sec != w && sec != -1) {
                ret = min(ret, ans - sec + w);
            }
        }
    }
    cout << ((ret == LLONG_MAX) ? -1 : ret);
    return 0;
}