백준 23314 - Minimum Spanning Cactus (C++)

문제

• 문제 링크

  
   BOJ 23314 - Minimum Spanning Cactus 
  

• 문제 요약

$N$개의 정점과 이들을 잇는 무향 가중치 간선 $M$개로 이루어진 $Cactus$ $Graph$가 주어진다.
아래 쿼리를 수행하는 프로그램을 작성하자.



$u$ $v$ $d$ : 정점 $u$와 정점 $v$를 잇는 간선의 가중치를 $d$로 바꾸고, 최소 신장 선인장의 비용을 출력한다.


• 제한

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




$2 ≤ N ≤ 100,000$

$N-1 ≤ M ≤ 150,000$

$1 ≤ Q ≤ 100,000$

$-10^9 ≤ c ≤ 10^9$

알고리즘 분류

• 자료 구조 (data_structures)
• 그래프 이론 (graphs)
• 이중 연결 요소 (biconnected_component)
• 선인장 (cactus)
• 트리를 사용한 집합과 맵 (tree _ set / map)

풀이

간선 $e$가 정점 $u, v$를 이을 때, $e$가 $u, v$의 연결성을 보장하는 유일한 간선이라면 $e$는 반드시 최소 신장 선인장에 포함되어야 한다.

반대로 $e$가 사이클 위에 존재했다면 기호에 따라 버릴 수도, 포함할 수도 있을 것이다.

즉, $e_w$가 음수라면 반드시 포함해야 이득일테고 양수라면 버리는 것이 이득이다.
만약 사이클에 $e_w > 0$인 간선이 여러 개라면 가장 큰 가중치만 버려야 한다. 연결성을 유지해야 하니 말이다.

---

$e_i$가 $articulation$ $edge$인지 빠르게 판단할 수 있도록 $biconnected$ $component$들을 모두 찾아보자.

이때, 임의 간선의 가중치를 실시간으로 변경할 수 있어야 하며 임의 $bcc$ 내 가장 큰 가중치를 실시간으로 받아올 수 있어야 한다.

$bcc$별로 집합을 만들자. 저장 형태는 {$e_w, e_u, e_v$} 로 해둘 수 있다.

어떤 간선이 몇 번째 $bcc$에 존재하는지 식별할 수 있도록 인덱스를 적어두자.

구체적으로, $rec[i]$ : $i$번째 간선이 속해있는 $bcc$의 번호.$($$-1$이라면 $e_i$는 $bcc$에 속하지 않음$)$

단, $bcc$가 단순 사이클을 이뤄야 하므로 하나의 간선으로 구성되는 $bcc$는 버려주도록 하자.

---

최초의 최소 신장 선인장 비용을 계산해보자.

이는 간단하게, 다음의 과정을 거쳐 계산할 수 있다.

모든 간선의 비용을 더한다.

모든 $bcc$들을 순회하며, 가장 큰 가중치의 값을 본다.

그 가중치가 양수라면 답에서 빼준다.

---

이제 모든 전처리가 끝났고, 쿼리를 처리해보자.

앞서 말했듯이 변경하고자 하는 간선 $e$가 $articulation$ $edge$라면 답은 간단하다.

기존 가중치를 $w$, 변경 가중치를 $d$라고 할 때 $ans = ans + d - w$.


$bcc$에 속해 있는 간선이라면 해당 $bcc$에서의 $e$를 업데이트 해주며, $d > 0$일 때와 $d ≤ 0$일 때로 나눠보자.

$d > 0$

• $e$가 기존 $bcc$의 가장 큰 간선이었을 때,
  • 변경 후 가장 큰 간선이 아니게 됐다면 $?$
  • 변경 후에도 가장 큰 간선이라면 $?$
• $e$가 기존 $bcc$의 가장 큰 간선이 아니었을 때,
  • 변경 후에도 가장 큰 간선이 아니라면 $?$
  • 변경 후 가장 큰 간선이 됐다면 $?$

$d ≤ 0$

• $e$가 기존 $bcc$의 가장 큰 간선이었을 때 $?$
• $e$가 기존 $bcc$의 가장 큰 간선이 아니었을 때 $?$

위의 어지러운 $case$_$work$가 끝나면 문제를 해결할 수 있다..

사실 몇 번의 시행착오를 거치다 포기 했었는데, $4$일 뒤$?$ 갑자기 고려하지 않은 부분이 번뜩였다.

최종 반례였던 케이스는 문제 게시판에 남겨 뒀으니 참고하면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define T tuple <int, int, int>
#define N 100001
using namespace std;
 
map <int, pair<int, int>> M[N];
vector <int> in(N), rec(N << 1, -1);
vector <set<T>> bcc;
 
stack <T> st; int cur;
int getBCC(int now, int prev)
{
    int _min(in[now] = ++cur);
    for (auto& [nxt, edge] : M[now])
    {
        auto& [weight, idx](edge);
        if (nxt == prev) continue;
        if (in[now] > in[nxt]) st.push({ weight, now, nxt });
        if (!in[nxt])
        {
            int temp(getBCC(nxt, now));
            if (in[now] <= temp)
            {
                vector <T> V;
                while (1)
                {
                    auto [w, u, v](st.top()); st.pop();
                    V.emplace_back(w, min(u, v), max(u, v));
                    rec[M[u][v].second] = bcc.size();
 
                    if (T(w, u, v) == T(weight, now, nxt)) break;
                }
                if (V.size() > 2)
                    bcc.emplace_back(set <T>(V.begin(), V.end()));
                else
                    for (auto& [w, u, v] : V)
                        rec[M[u][v].second] = -1;
            }
            _min = min(_min, temp);
        }
        _min = min(_min, in[nxt]);
    }
    return _min;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
 
    long long ans{};
    for (int u, v, w, i{}; i++ < m; ans += w)
    {
        cin >> u >> v >> w;
        M[u][v] = M[v][u] = { w, i };
    }
 
    getBCC(1, 1);
    for (auto& _bcc : bcc)
    {
        int val(get<0>(*--_bcc.end()));
        if (val > 0)
            ans -= val;
    }
 
    cout << ans << '\n';
    for (int u, v, d; q--;)
    {
        cin >> u >> v >> d;
        if (u > v) swap(u, v);
        auto [w, i](M[u][v]);
        int b_i(rec[i]);
 
        M[v][u].first = M[u][v].first = d;
        if (!~b_i)
        {
            cout << (ans += d - w) << '\n';
            continue;
        }
 
        auto end(*--bcc[b_i].end());
        bcc[b_i].erase(T(w, u, v));
        bcc[b_i].insert(T(d, u, v));
        auto _end(*--bcc[b_i].end());
 
        if (d > 0)
        {
            if (end == T(w, u, v))
            {
                if (_end != T(d, u, v))
                {
                    int val(get<0>(_end));
                    ans += (val > 0 ? -val : 0) + d;
                }
                else ans -= w > 0 ? 0 : w;
            }
            else
            {
                if (_end != T(d, u, v)) ans += d - w;
                else
                {
                    int val(get<0>(end));
                    ans += (val > 0 ? val : 0) - w;
                }
            }
        }
        else
        {
            if (end == T(w, u, v))
            {
                ans += d - (w > 0 ? 0 : w);
                int val(get<0>(_end));
                ans -= val > 0 ? val : 0;
            }
            else ans += d - w;
        }
        cout << ans << '\n';
    }
}

comment

이렇게 말고, 좀 더 깔끔하고 명료한 풀이가 있을 것 같은데 어렵게 푼 게 아닌가 싶다.
여튼 $AC$면 장땡. 재밌게 푼 문제였다.


여담으로 문제를 푼 사람들은 알겠지만, 채점 결과 시간에 비해 채점 진행 속도가 굉장히 느리다.
나도 처음에 $TLE$를 맞는 건가 쫄았지만 기여 탭을 보면 채점 데이터가 무려 $300$개가 넘는다고 한다.

파이썬 유저라면 서버비 내야 할듯.