boj 15481 그래프와 MST

www.acmicpc.net/problem/15481

15481번: 그래프와 MST

M개의 간선 정보가 들어오는데 i번째 간선을 포함한 MST를 출력하는 문제입니다.

 

우선 전체 MST를 구해줍니다.

그 다음 i번째 간선을 포함해주고 그 간선에 연결된 정점들의 경로에 있는 MST 간선을 하나 제거해야합니다.

이 경로를 순회해야 하기때문에 이를 LCA로 구합니다.

 

여기서 LCA를 구하기 전에 각 정점의 높이를 구해야하는데 인접 리스트를 MST 간선들만 가지고 구해줍니다.

그럼 u v 경로의 최대 간선을 구할 수 있습니다.

 

답은 mst - lca(u, v) + w을 출력해주시면 되고, 입력이 들어온 순서대로 출력해야하니 인덱스를 유지해야합니다.

 

정리하자면

1. 먼저 주어진 간선들로 MST를 구합니다.

2. MST에 사용된 간선들로 인접 리스트를 만들어줍니다.

3. 인접리스트의 depth를 구합니다.

4. 입력(간선 정보)이 들어왔던 순서대로 lca를 구해줍니다.

5. mst - lca(u, v) + w을 출력합니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200000
#define LOG 20
using namespace std;
typedef long long ll;
 
typedef struct edge {
    int u;
    int v;
    ll w;
}edge;
 
vector<pair<int, ll> > list[MAX + 1];
vector<edge> v, nv;
pair<int, ll> lcaParent[MAX + 1][LOG];
int mstParent[MAX + 1], depth[MAX + 1];
bool visit[MAX + 1];
ll mst;
int N, M, cnt;
 
bool cmp(edge a, edge b) {
    return a.w < b.w;
}
 
void dfs(int v, int d) {
    depth[v] = d;
    visit[v] = true;
 
    for (int i = 0; i < list[v].size(); i++) {
        int next = list[v][i].first;
        ll w = list[v][i].second;
 
        if (visit[next]) continue;
        lcaParent[next][0] = { v,w };
        dfs(next, d + 1);
    }
}
 
int find(int v) {
    if (mstParent[v] == v) return v;
    return mstParent[v] = find(mstParent[v]);
}
 
void Union(int x, int y, ll w) {
    int a = find(x);
    int b = find(y);
 
    if (a == b) return;
    list[x].push_back({ y,w });
    list[y].push_back({ x,w });
    mstParent[b] = a;
    mst += w;
    cnt++;
}
 
void makeMst() {
    for (int i = 0; i < M; i++) {
        int x = nv[i].u;
        int y = nv[i].v;
        ll w = nv[i].w;
 
        Union(x, y, w);
        if (cnt == N - 1) break;
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        mstParent[i] = i;
    }
}
 
ll lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);
    ll ret = 0;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[y] - depth[x] >= (1 << i)) {
            ret = max(ret, lcaParent[y][i].second);
            y = lcaParent[y][i].first;
        }
    }
 
    if (x == y) return ret;
 
    for (int i = LOG - 1; i >= 0; i--) {
        if (lcaParent[x][i].first == 0) continue;
        if (lcaParent[x][i].first != lcaParent[y][i].first) {
            ret = max(ret, max(lcaParent[x][i].second, lcaParent[y][i].second));
 
            x = lcaParent[x][i].first;
            y = lcaParent[y][i].first;
        }
    }
 
    return max(ret, max(lcaParent[x][0].second, lcaParent[y][0].second));
}
 
void func() {
    dfs(1, 1);
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= N; i++) {
            lcaParent[i][j].first = lcaParent[lcaParent[i][j - 1].first][j - 1].first;
            lcaParent[i][j].second = max(lcaParent[i][j - 1].second, lcaParent[lcaParent[i][j - 1].first][j - 1].second);
        }
    }
 
    for (int i = 0; i < M; i++) {
        int x = v[i].u;
        int y = v[i].v;
        ll w = v[i].w;
        ll sub = lca(x, y);
        cout << mst - sub + w << '\n';
    }
}
 
void input() {
    int x, y;
    ll w;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> x >> y >> w;
        v.push_back({ x,y,w });
    }
    nv = v;
    sort(nv.begin(), nv.end(), cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    init();
    makeMst();
    func();
 
    return 0;
}