[백준] 1626: 두 번째로 작은 스패닝 트리

0. 문제 주소

 

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

1626번: 두 번째로 작은 스패닝 트리

 

 

1. 풀이

 

*** 첫 다이아 문제 ***

 

기본 아이디어는 다음과 같다.

 

0. 크루스칼 알고리즘을 이용해 MST를 만든다. 기존 그래프와 별도로 만들어줄 것이고, 사용하지 않은 간선들은

  notused_PQ(min heap)에 따로 넣어준다. 여기서 MST가 안 만들어지면 -1을 출력한다.

1. 만든 MST로 LCA sparse table을 두 개 만든다.

   1-1. lcaP[i][j] = i번 노드의 2^j번째 부모

   1-2. max_values[i][j] = i번 노드부터 2^j번째 부모 사이의 간선 중에서 pair( 가중치가 가장 큰 간선, 두 번째로 큰 간선)

    * 여기서 두 번째로 큰 값이 없으면(전부 다 같은 값이거나, 값 후보가 하나이거나 등) -1로 초기화 해 둔다.

      가장 큰 값과 두 번째로 큰 값을 반드시 다르게 만들기 위한 작업이다.

2. notused_PQ에서 간선을 하나씩 뽑아 기존 MST의 간선들 중 하나와 교체할 것이다.

   2-1. 새로 뽑은 간선을 MST에 추가시키면, 사이클이 무조건 생기게 된다.

   2-2. 사이클 내에서, 새로운 간선을 제외한 나머지 간선들 중에, 가장 큰 가중치를 가지는 간선과

    새로운 간선을 교체한다. max_values sparse table을 이용한다.

    사이클 내에서만 교체가 일어나야 여전히 spanning tree의 조건을 만족하기 때문이다.

   2-3. 2-2.에서, 가장 큰 가중치를 갖는 간선의 가중치가 새로운 간선의 가중치와 같다면, 두 번째로 큰 가중치를 갖는

    간선과 교체한다.

   2-4. 2-3.에서, 두 번째로 큰 가중치가 -1로 초기화되어 있다면, 이 사이클에선 더 이상 볼 간선이

    남아있지 않다는 뜻이므로, 더 이상 교체하지 않는다.

3. 2를 반복하며 새로 만들어진 스패닝 트리들 중 간선의 합이 가장 작은 것이 답이다.

   * 전처리 덕분에 기존 MST와 같은 값을 가지는지는 고려하지 않아도 된다.

 

 

문제에 이런 표현이 있다.

 

방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다.

 

근데 또 출력 조건에는 이런 표현이 있다.

 

만약 스패닝 트리나 두 번째로 작은 스패닝 트리가 존재하지 않는다면 -1을 출력한다.

 

문제에 있는 표현만 보고 스패닝 트리가 무조건 만들어지는 그래프만 준다고 생각해서 헤매다가, 질문들을 찾아보고 겨우 고쳤다.

 

또 하나 실수했던 점은, lca를 찾아 나가는 과정에서 u와 v의 depth를 같게 해주고 난 뒤,

u와 v가 같지 않을 때에만 올려나가야 하는데 그 조건을 안 써서 고생했었다.

 

지금까지 풀었던 문제 중에 가장 뿌듯했던 문제.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define MAX 50005
#define PMAX 18
#define pii pair<int, int>
#define piii pair<int, pii>
#define ll long long
#define INF 9876543210LL

using namespace std;

int V, E;
int p[MAX];
ll total_edge_value;
ll MST_value;
vector<pii> graph[MAX];

priority_queue<piii, vector<piii>, greater<piii>> PQ;
priority_queue<piii, vector<piii>, greater<piii>> notused_PQ;
vector<pii> MST[MAX];
int depth[MAX];
int lcaP[MAX][PMAX];
pii max_values[MAX][PMAX];

int find(int node){
    if (p[node] == -1) return node;
    
    return p[node] = find(p[node]);
}

void merge(int a, int b){
    int roota = find(a);
    int rootb = find(b);
    
    if (roota == rootb) return;
    p[roota] = rootb;
    return;
}

void maketree(int curr){
    for (auto p: MST[curr]){
        int next = p.first, weight = p.second;
        if (depth[next] == -1){
            depth[next] = depth[curr] + 1;
            lcaP[next][0] = curr;
            max_values[next][0] = pii(weight, -1);
            maketree(next);
        }
    }
    return;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    memset(p, -1, sizeof(p));
    scanf("%d %d", &V, &E);
    
    
    for (int i=0;i<E;i++){
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        total_edge_value += c;
        graph[u].push_back(pii(v, c));
        graph[v].push_back(pii(u, c));
        PQ.push(piii(c, pii(u, v)));
    }
    
    int edge_cnt = 0;
    while(!PQ.empty()){
        auto pp = PQ.top();
        PQ.pop();
        int weight = pp.first, u = pp.second.first, v = pp.second.second;
        if (find(u) != find(v)){
            merge(u, v);
            MST[u].push_back(pii(v, weight));
            MST[v].push_back(pii(u, weight));
            MST_value += weight;
            edge_cnt++;
        }
        else{
            notused_PQ.push(piii(weight, pii(u, v)));
        }
    }
    
    if (edge_cnt != V-1 || E <= V-1){
        printf("-1\n");
        return 0;
    }
    
    for (int i=1;i<=V;i++){
        for (int j=0;j<PMAX;j++){
            max_values[i][j] = pii(-1, -1);
        }
    }
    memset(lcaP, -1, sizeof(lcaP));
    memset(depth, -1, sizeof(depth));
    depth[1] = 0;
    maketree(1);
    
    for (int j=0;j<PMAX-1;j++){
        for (int i=1;i<=V;i++){
            if (lcaP[i][j] != -1){
                lcaP[i][j+1] = lcaP[lcaP[i][j]][j];
                if (lcaP[i][j+1] == -1) continue;
                pii half_below = max_values[i][j];
                int a = half_below.first, b = half_below.second;
                pii half_above = max_values[lcaP[i][j]][j];
                int c = half_above.first, d = half_above.second;
                vector<int> temp = {a, b, c, d};
                sort(temp.begin(), temp.end(), greater<int>());
                
                int firstmax = -1, secondmax = -1;
                
                for (int n: temp){
                    firstmax = max(firstmax, n);
                }
                
                for (int n: temp){
                    if (n==firstmax) continue;
                    secondmax = max(secondmax, n);
                }
                max_values[i][j+1] = pii(firstmax, secondmax);
            }
        }
    }
    
    ll ans = INF;
    while(!notused_PQ.empty()){
        auto pp = notused_PQ.top();
        notused_PQ.pop();
        int new_weight = pp.first, new_u = pp.second.first, new_v = pp.second.second;
        
        int firstmax = -1, secondmax = -1;
        int u = new_u, v = new_v;
        
        if (depth[u] < depth[v]) swap(u, v);
        
        
        int diff = depth[u] - depth[v];
        
        for (int i=0;diff;i++){
            if (diff%2) {
                int a = max_values[u][i].first, b = max_values[u][i].second;
                vector<int> temp = {firstmax, secondmax, a, b};
                sort(temp.begin(), temp.end(), greater<int>());
                firstmax = temp[0];
                for (int n:temp){
                    if (n==firstmax) continue;
                    secondmax = max(secondmax, n);
                }
                u = lcaP[u][i];
            }
            diff /= 2;
            
        }
        
        if (u != v) {
            for (int j=PMAX-1;j>=0;j--){
                if (lcaP[u][j] != -1 && lcaP[u][j] != lcaP[v][j]){
                    int a = max_values[u][j].first, b = max_values[u][j].second;
                    int c = max_values[v][j].first, d = max_values[v][j].second;
                    vector<int> temp = {a, b, c, d, firstmax, secondmax};
                    sort(temp.begin(), temp.end(), greater<int>());
                    firstmax = temp[0];
                    for (int n: temp){
                        if (n==firstmax) continue;
                        secondmax = max(secondmax, n);
                    }
                    
                    u = lcaP[u][j];
                    v = lcaP[v][j];
                }
            }
            
            int a = max_values[u][0].first, b = max_values[u][0].second;
            int c = max_values[v][0].first, d = max_values[v][0].second;
            vector<int> temp = {a, b, c, d, firstmax, secondmax};
            sort(temp.begin(), temp.end(), greater<int>());
            firstmax = temp[0];
            for (int n: temp){
                if (n == firstmax) continue;
                secondmax = max(secondmax, n);
            }
        }
        
        if (firstmax != new_weight){
            ll curr_ST_value = MST_value - firstmax + new_weight;
            ans = min(ans, curr_ST_value);
        }
        else if (secondmax != -1){
            ll curr_ST_value = MST_value - secondmax + new_weight;
            ans = min(ans, curr_ST_value);
        }
    }
    
    if (ans == INF) {
        printf("-1\n");
    }
    else{
        printf("%lld\n", ans);
    }
    
    return 0;
}