백준 1626 - 두 번째로 작은 스패닝 트리 (C++)

문제

• 문제 링크

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

• 문제 요약

$V$개의 정점으로 이루어진 무향 그래프가 주어진다.
이 그래프의 '두 번째로 작은 스패닝 트리'를 구해보자.

• 제한

TL : $2$ sec, ML : $128$ MB




$1 ≤ V ≤ 50,000$

$1 ≤ E ≤ 200,000$

$0 ≤ E_w ≤ 100,000$

알고리즘 분류

• 자료 구조(data structures)
• 그래프 이론(graphs)
• 트리(trees)
• 최소 스패닝 트리(minimum spanning tree)
• 최소 공통 조상(lowest common ancestor)
• 희소 배열(sparse table)

풀이

이 문제 를 풀어 보았는가 ?
비슷하면서, 다르기도 하다.

위 문제는 $LCA$ $with$ $Sparse$ $Table$ 로 쉽게 해결할 수 있었다.
구체적으로 $Sparse$ $Table$ 에서 $2^x$ 꼴 부모를 저장함과 동시에 해당 시점의 가장 큰 가중치도 함께 저장해 해결할 수 있다.

그러나 이번 문제에서는 $The$ $second$ $minimum$ $spanning$ $tree$ ( 이하 $sst$ ) 를 구해야 한다.
결론부터 말하면, 가장 큰 가중치 이외에 두번째로 큰 가중치 도 함께 저장해야 한다. 왤까?

---

우선 $mst$를 돌리면서, 사용되지 않는 간선이라고 버리지 말고 따로 모아두자. ( $NEg[]$ )
이들은 나중에 $sst$를 구성할 수도 있는 귀중한 후보군들이다.

우리가 찾는 $sst$엔 절대적인 조건이 있다. 바로 $W_{sst} > W_{mst}$를 만족해야 한다는 것이다.
위에서 말한 가장 큰 가중치를 특정해서 $sst$를 만들 때, 만약 기존 $mst$의 가중치와 같으면 어떡할 것인가?

이럴 때 바로 $sst$가 없다고 판단하여 $-1$을 출력하거나 해당 시점을 $pass$ 해 버린다면 모든 가능성을 확인해 보지도 않았는데 답을 특정하려 하게 된다.

따라서 두 번째로 큰 가중치를 고려해야 하는데, 이를 전처리 하는 것이 조금 까다로울 수 있다.
같은 시점에서 가장 큰 가중치의 눈치를 보면서 값을 담아야 하는데 $LCAInit2()$ 함수를 보는 것이 나을 것 같다.

---

이제 $NEg[]$를 순회해 보며 $sst$를 특정해야 하는데 그 전에 $mst$가 존재 하는게 보장되지 않는다.
이 경우에 대한 예외 처리를 잊지 말자.

$NEg[i]$가 정점 $u, v$를 가중치 $w$로 이을 때 $sst$의 비용은 $s - g + w$ 라 할 수 있다.
여기서 $s, g$의 의미는 다음과 같다.

$s$ : 최초 $mst$ 구축 비용.

$g :$ 정점 $u, v$ 를 잇는 경로 상에 가장 큰 가중치. ( 단, $g$는 반드시 특정 되어 있어야 하며 $w$와 같지 않아야 한다. )

$g == w$ 가 되어 버리면, 결국 간선 다른 $mst$를 다시 구한 셈이 되니 말이다.

$GetLCA()$ 에서 $Sparse$ $Table$ 을 이용해 $lifting$ 하는 건 $LCA$ 기본 문제 수준이니 별다른 설명은 생략하겠다.
이 과정에서 하나 유의 할 건 앞서 말한 $g < w$ 의 조건을 유의하자.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 50001
using namespace std;
 
struct E
{
    int v1, v2, w;
    bool operator<(E& e) { return w < e.w; }
}Eg[200001];
vector <pair<int, int>> Gr[N];
vector <E> NEg;
int dp[N][17], mdp[N][17], sdp[N][17];
int n, m, s, P[N], D[N];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(P, P + N, 0); cin >> n >> m;
    for (int i{}; i < m; i++)
        cin >> Eg[i].v1 >> Eg[i].v2 >> Eg[i].w;
}
int Find(int p) { return P[p] = P[p] == p ? p : Find(P[p]); }
void MST(int c = 0)
{
    sort(Eg, Eg + m);
    for (int i{}; i < m; i++)
    {
        int p(Find(Eg[i].v1)), q(Find(Eg[i].v2));
        if (p == q) NEg.push_back(Eg[i]);
        else
        {
            s += Eg[i].w; c++;
            Gr[Eg[i].v1].emplace_back(Eg[i].v2, Eg[i].w);
            Gr[Eg[i].v2].emplace_back(Eg[i].v1, Eg[i].w);
            p > q ? P[p] = q : P[q] = p;
        }
    }
    if (c < n - 1) cout << -1, exit(0);
}
void LCAInit1(int x, int d)
{
    D[x] = d;
    for (auto& [p, q] : Gr[x])
        if (!D[p])
        {
            mdp[p][0] = q, sdp[p][0] = -1;
            dp[p][0] = x;
            LCAInit1(p, d + 1);
        }
}
void LCAInit2()
{
    for (int j(1); j < 17; j++)
        for (int i(1); i <= n; i++)
        {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
            mdp[i][j] = max(mdp[i][j - 1], mdp[dp[i][j - 1]][j - 1]);
            int p(max(mdp[i][j - 1] == mdp[i][j] ? -1 : mdp[i][j - 1], mdp[dp[i][j - 1]][j - 1] == mdp[i][j] ? -1 : mdp[dp[i][j - 1]][j - 1]));
            int q(max(sdp[i][j - 1] == mdp[i][j] ? -1 : sdp[i][j - 1], sdp[dp[i][j - 1]][j - 1] == mdp[i][j] ? -1 : sdp[dp[i][j - 1]][j - 1]));
            sdp[i][j] = max(p, q);
        }
}
int GetLCA(int p, int q, int z)
{
    if (D[p] < D[q]) swap(p, q);
    int g(-1), d = D[p] - D[q];
    for (int i{}; d; d >>= 1, i++)
        if (d & 1)
            g = max(g, mdp[p][i] ^ z ? mdp[p][i] : sdp[p][i]), p = dp[p][i];
    if (p ^ q)
    {
        for (int i(16); !!~i; i--)
            if (dp[p][i] ^ dp[q][i])
            {
                g = max(g, mdp[p][i] ^ z ? mdp[p][i] : sdp[p][i]);
                g = max(g, mdp[q][i] ^ z ? mdp[q][i] : sdp[q][i]);
                p = dp[p][i], q = dp[q][i];
            }
        g = max(g, mdp[p][0] ^ z ? mdp[p][0] : sdp[p][0]);
        g = max(g, mdp[q][0] ^ z ? mdp[q][0] : sdp[q][0]);
    }
    return g;
}
void Solve(ll r = 1e12)
{
    for (int i(NEg.size() - 1); !!~i; i--)
        if (n = GetLCA(NEg[i].v1, NEg[i].v2, NEg[i].w); !!~n)
            if (ll k = (ll)s - n + NEg[i].w; k > s && k < r)
                r = k;
    cout << (r == 1e12 ? -1 : r);
}
int main()
{
    Init();
    MST();
    LCAInit1(1, 1);
    LCAInit2();
    Solve();
}

comment

개인적으로 좋아하는 문제이고, 첫 다이아 문제였어서 더 기억에 남는 문제이다.
두작스는 명작이 맞다..