백준 20132 - Parity Constraint Minimum Spanning Tree (C++)

문제

• 문제 링크

  
   BOJ 20132 - Parity Constraint Minimum Spanning Tree 
  

• 문제 요약

$N$개의 정점과 $M$개의 간선으로 이루어진 무향 그래프가 주어진다.
이 그래프의 스패닝 트리에서, 비용이 홀수인 최솟값과 짝수인 최솟값을 구헤보자.

• 제한

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




$2 ≤ N ≤ 100,000$

$1 ≤ M ≤ 300,000$

$1 ≤ w_i ≤ 1,000,000,000$

알고리즘 분류

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

풀이

BOJ 1626 - 두 번째로 작은 스패닝 트리 와 BOJ 15481 - 그래프와 MST 의 중간 그 어딘가에 있는 듯한 문제였다.

기본적인 흐름은 위 문제들과 비슷하다.

우선 $mst$를 생각해보자.
이 때의 비용보다 작은 스패닝 트리는 존재할 수 없으며, 이 값이 곧 정답이다.
문제는 반대(홀수 - 짝수)의 최소 비용을 어떻게 구하냐이다.

크루스칼로 최초 $mst$를 구축하는 과정에서, 여기에 포함되는 간선들로 새로이 트리를 만들자.
또한 간선마다 포함 여부를 나타내는 변수를 추가해 사용 여부를 구분할 수 있도록 하자.

사용되지 않은 간선들은, 반대의 최소 비용을 구함에 있어서 쓰일 가능성이 있는 귀중한 녀석들이다.

---

홀수, 짝수 이전에 우린 '최솟값'을 구해야 한다.
만약 기존 스패닝 트리에서 새로운 간선 $e$를 포함해야 한다면, 다음을 따르는 것이 자명하다.

$e$가 정점 $u, v$를 이을 때, 기존 $u, v$를 잇는 경로 상의 가중치가 가장 큰 간선 $l$을 제외해야 한다.

이때 발생하는 비용은 $Cost_{mst} + Cost_e - Cost_l$

이때 $Cost_l$은 $Sparse$ $Table$을 이용한 $Binary$ $Lifting$으로 전처리 $O(NlogN)$, 쿼리 당 $O(logN)$만에 쉽게 찾아낼 수 있다.

---

이제 좀 더 나아가서 $Cost_{mst}$가 홀수라면 짝수의 비용을, 짝수라면 홀수의 비용을 구해야 한다.

이에 따라 식 $Cost_{mst} + Cost_e - Cost_l$ 에서,

$Cost_e$가 홀수라면 $Cost_l$은 짝수여야 한다.

$Cost_e$가 짝수라면 $Cost_l$은 홀수여야 한다.

따라서 우리는 시점 $2^0, 2^1, ... 2^k$에 대해 총 $3$가지의 $Sparse$ $Table$을 전처리해야 한다.

구체적으로,

$dp[x][y] = x$의 $2^y$번째 조상

$od$_$dp[x][y] = x$와 $2^y$번째 조상을 잇는 단순 경로 상에서, 비용이 홀수인 최대 간선

$ev$_$dp[x][y] = x$와 $2^y$번째 조상을 잇는 단순 경로 상에서, 비용이 짝수인 최대 간선

가 되겠다.

이제 최초 $mst$구축에 사용되지 않은 간선들에 대해, 위의 작업을 적용하며 최솟값을 찾아주면 끝.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
 
vector <tuple<int, int, int, bool>> Eg;
vector <pair<int, int>> Gr[N];
int Dep[N], Par[N], dp[N][18];
int od_dp[N][18], ev_dp[N][18];
ll n, m, mst;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; Eg.resize(m);
    for (auto& [w, p, q, k] : Eg)
        cin >> p >> q >> w;
    sort(Eg.begin(), Eg.end());
}
int Find(int x) { return Par[x] = Par[x] == x ? x : Find(Par[x]); }
void MST()
{
    iota(Par, Par + N, 0);
    for (auto& [w, p, q, k] : Eg)
    {
        int x(Find(p)), y(Find(q));
        if (x ^ y)
        {
            x > y ? Par[x] = y : Par[y] = x;
            Gr[p].emplace_back(q, w);
            Gr[q].emplace_back(p, w);
            mst += w;
            k = 1;
        }
    }
}
void LCAInit(int p, int d)
{
    Dep[p] = d;
    for (auto& [x, y] : Gr[p])
        if (!Dep[x])
        {
            (y & 1 ? od_dp[x][0] : ev_dp[x][0]) = y;
            dp[x][0] = p;
            LCAInit(x, d + 1);
        }
}
void TableDP()
{
    for (int j(1); j < 18; j++)
        for (int i(1); i <= n; i++)
        {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
            od_dp[i][j] = max(od_dp[i][j - 1], od_dp[dp[i][j - 1]][j - 1]);
            ev_dp[i][j] = max(ev_dp[i][j - 1], ev_dp[dp[i][j - 1]][j - 1]);
        }
}
int GetLCA(int x, int y, int t)
{
    auto& wdp(t ? ev_dp : od_dp);
    if (Dep[x] < Dep[y]) swap(x, y);
 
    int d(Dep[x] - Dep[y]), w{};
 
    for (int i{}; d; d >>= 1, i++)
        if (d & 1)
        {
            w = max(w, wdp[x][i]);
            x = dp[x][i];
        }
    if (x ^ y)
    {
        for (int i(17); !!~i; i--)
            if (dp[x][i] ^ dp[y][i])
            {
                w = max({ w, wdp[x][i], wdp[y][i] });
                x = dp[x][i], y = dp[y][i];
            }
        w = max({ w, wdp[x][0], wdp[y][0] });
    }
    return w;
}
void Solve(ll ans)
{
    for (auto& [w, p, q, k] : Eg)
        if (!k)
            ans = min(ans, mst + w - GetLCA(p, q, w & 1));
    if (ans == 1e18) ans = -1;
    if (mst & 1) swap(ans, mst);
 
    cout << ans << ' ' << mst;
}
int main()
{
    Init();
    MST();
    LCAInit(1, 1);
    TableDP();
    Solve(1e18);
}

comment

끝