그래프와 MST (백준 15481)

안녕하세요. 오늘은 그래프에서 MST를 만들어볼 거예요.

문제

https://www.acmicpc.net/problem/15481

아이디어

일단 MST문제이므로 MST부터 만듭시다.
만약 어떤 간선이 그 MST에 포함이 되어 있다면 그냥 무조건 MST의 가중치를 출력해주면 됩니다.
만약 그 간선이 MST에 포함이 되어있지 않다면 어떻게 될까요?

u와 v를 잇는 간선이 있다고 합시다.
일단은 머릿속에 MST그래프를 진하게 그려놓고 연하게 기본 그래플 그려놓습니다. 그리고 u와 v를 잇는 연한 간선을 진하게 만들면 하나의 진한 사이클이 보입니다. 그 사이클에서 아무거나 하나를 빼서 전체 값이 최소가 되게 하면 됩니다. 그러려면 최댓값을 빼면 됩니다. 이때 당연하지만 u와 v를 잇는 간선이 최댓값이지만 빼면 안됩니다. 그래서 u와 v를 잇는 MST위의 경로중에서 최댓값을 찾아서 빼주면 됩니다. 이를 빠르게 찾으려면 최소 공통 조상 (LCA)알고리즘을 쓰는것이 편합니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll N;
vector <pair <ll, ll> > v[202020], MST[202020];

ll par[202020] = { 0 };
ll find(ll x)
{
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}
void Union(ll x, ll y)
{
    par[find(x)] = find(y);
}
bool same(ll x, ll y)
{
    return find(x) == find(y);
}
ll GetMST() //MST벡터에 MST그래프를 넣고 그 MST값을 반환하는 함수
{
    vector <pair <ll, pair <ll, ll> > > graph;
    for (ll i = 1; i <= N; i++)
        for (auto temp:v[i])
        {
            ll j = temp.first, val = temp.second;
            if (i < j) continue;
            graph.push_back({ val, { i,j } });
        }
    for (ll i = 1; i <= N; i++) par[i] = i;

    ll ans = 0, M = graph.size();
    sort(graph.begin(), graph.end());
    for (ll i = 0; i < M; i++)
    {
        if (same(graph[i].second.first, graph[i].second.second)) continue;
        Union(graph[i].second.first, graph[i].second.second);
        ans += graph[i].first;
        MST[graph[i].second.first].push_back({ graph[i].second.second,graph[i].first });
        MST[graph[i].second.second].push_back({ graph[i].second.first,graph[i].first });
    }
    return ans;
}

ll parent[202020][20] = { 0 }, mx[202020][20] = { 0 }, depth[202020] = { 0 };
void DFS(ll node, ll up)
{
    depth[node] = depth[up] + 1;
    parent[node][0] = up;
    for (ll i = 1; i < 20; i++)
    {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
        mx[node][i] = max(mx[node][i - 1], mx[parent[node][i - 1]][i - 1]);
    }
    for (auto next : MST[node])
    {
        if (next.first != up)
        {
            mx[next.first][0] = next.second;
            DFS(next.first, node);
        }
    }
}
ll GetMX(ll x, ll y)
{
    ll ans = 0;
    if (depth[x] < depth[y]) swap(x, y);
    for (ll i = 19; i >= 0; i--)
    {
        if (depth[parent[x][i]] >= depth[y])
        {
            ans = max(ans, mx[x][i]);
            x = parent[x][i];
        }
    }
    if (x == y) return ans;
    for (ll i = 19; i >= 0; i--)
    {
        if (parent[x][i] != parent[y][i])
        {
            ans = max(ans, max(mx[x][i], mx[y][i]));
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    ans = max(ans, max(mx[x][0], mx[y][0]));
    return ans;
}


int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, i, a, b, c;
    vector <pair <pair <ll,ll>, ll> > edges;

    cin >> N >> M;
    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
        edges.push_back({ {a,b},c });
    }
    ll MST_value = GetMST();
    DFS(1, 0);

    for (i = 0; i < M; i++)
    {
        a = edges[i].first.first;
        b = edges[i].first.second;
        c = edges[i].second;

        if (parent[a][0] == b || parent[b][0] == a) //만약 a와 b를 잇는 간선이 MST에 포함되어있다면
            cout << MST_value << "\n";
        else
            cout << MST_value - GetMX(a, b) + c << "\n"; //전체-최대+지금이거
    }
}

감사합니다.