백준 15060 - Imperial roads (C++)

문제

• 문제 링크

  
   BOJ 15060 - Imperial roads 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프가 주어진다.
$Q$개의 쿼리로 정점 쌍들이 주어지는데, 이 정점 쌍을 직접적으로 잇는 간선을 포함한 $MST$의 비용을 출력하자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ N ≤ 10^5$

$N − 1 ≤ R ≤ 2 * 10^5$

알고리즘 분류

• 그래프 이론(graphs)
• 트리(trees)
• 최소 스패닝 트리(minimum spanning tree)
• 최소 공통 조상(lowest common ancestor)

풀이

주어진 그래프에 대해, 최소 비용만을 따진 채 모든 정점을 연결 시켜야 하므로 우선 $MST$를 구축해보자. $(G)$
이제 $G$에 임의의 정점 쌍 $(i, j)$를 직접적으로 연결하는 간선$(E)$을 포함 시키려 한다고 해보자.

해당 간선이 이미 $G$에 포함 되어 있다면, $G$를 구성할 때 들었던 비용이 곧 답이다.

해당 간선이 $G$에 포함 되어 있지 않다면 $??$

---

두번째 문제에 대해 $G$의 입장에서 생각해보자.
현재 사이클 없는 트리의 형태인데, $E$가 추가 되면 $(i, j)$ 근방에 사이클이 형성 되어 버린다.

이에 따라 해당 사이클에서 간선 하나를 지워야만 기존 $G$의 형태를 유지할 수 있다.
그리고 이땐 당연하게도, 계속해서 $Minimum$ $Spanning$ $Tree$를 유지해야 하기 때문에 $E$를 제외한 가중치가 가장 큰 간선을 지워야 한다.

이 작업은 $LCA$ $With$ $Sparse$ $Table$ 을 이용하면 쿼리당 $O(logN)$ 수준으로 간선을 찾아낼 수 있게 된다.

---

$LCA$의 $Binary$ $Lifting$을 위한 기본적인 전처리를 하면서, 가장 큰 가중치와 관련된 전처리도 함께 진행하자.

구체적으로 $dp[x][y]$에 정점 $x$의 $2^y$번째 부모를 저장한다면 $mdp[x][y]$에는 정점 $x$부터 $2^y$번째 부모까지의 경로 상 가장 큰 가중치를 저장하자.

최종적으로 $G$의 비용을 $s$, $E$의 가중치를 $E_{cost}$, $(i, j)$의 경로 상 가장 큰 가중치를 $x$라 한다면

쿼리마다 답은 $s - x + E_{cost}$ 가 되겠다.

어떤 쿼리가 주어질 지 모르니 임의의 간선 정보를 편히 빼올 수 있도록 $Hash$_$Map$ 을 이용했다.
이때 일반성을 유지 하도록 정점 쌍 $(i, j)$에 대해 $i < j$ 의 형태로 저장 및 사용 하도록 하자.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <tuple<int, int, int>> Eg;
vector <pair<int, int>> Gr[N];
unordered_map <int, int> M[N];
int D[N], P[N], dp[N][18], mdp[N][18];
int n, m, q, s;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i, j, w; m--; M[i][j] = w)
    {
        cin >> i >> j >> w;
        if (i > j) swap(i, j);
        Eg.emplace_back(w, i, j);
    }
}
int Find(int p) { return P[p] = P[p] == p ? p : Find(P[p]); }
void MST()
{
    sort(Eg.begin(), Eg.end());
    iota(P, P + N, 0);
    for (auto& [w, i, j] : Eg)
        if (int x(Find(i)), y(Find(j)); x ^ y)
        {
            x > y ? P[x] = y : P[y] = x;
            Gr[i].emplace_back(j, w);
            Gr[j].emplace_back(i, w);
            s += w;
        }
}
void LCAInit(int p, int d)
{
    D[p] = d;
    for(auto& [x, y] : Gr[p])
        if (!D[x])
        {
            dp[x][0] = p, mdp[x][0] = y;
            LCAInit(x, d + 1);
        }
}
void SparseTableDP()
{
    for(int j(1); j < 18; 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 GetLCACost(int p, int q)
{
    if (D[p] < D[q]) swap(p, q);
    int d(D[p] - D[q]), g{};
    for (int i{}; d; d >>= 1, i++)
        if (d & 1)
            g = max(g, mdp[p][i]), p = dp[p][i];
    if (p ^ q)
    {
        for (int i(17); !!~i; i--)
            if (dp[p][i] ^ dp[q][i])
            {
                g = max({ g, mdp[p][i], mdp[q][i] });
                p = dp[p][i], q = dp[q][i];
            }
        g = max({ g, mdp[p][0], mdp[q][0] });
    }
    return g;
}
void Solve()
{
    for (cin >> q; q--;)
    {
        int i, j; cin >> i >> j;
        if (i > j) swap(i, j);
        cout << s + M[i][j] - GetLCACost(i, j) << '\n';
    }
}
int main()
{
    Init();
    MST();
    LCAInit(1, 1);
    SparseTableDP();
    Solve();
}

comment

끝