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

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

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

---

이 문제를 해결 하기 위해서는 우선 밑의 문제를 풀 수 있어야 한다.

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

15481번: 그래프와 MST

위의 문제와 비슷한 아이디어로 풀긴 하지만 좀 더 까다롭다.

(초기 MST를 구성하면서, 모든 정점을 방문하지 못한다면, -1를 출력하면 된다.)

{u , v , w} 의 정보를 갖는 새로운 간선을 삽입 할 경우

(기존 mst의 간선의 총합)-(u와v의 간선중 가장 큰 경로)+(w)

가 기존 (기존 mst의 간선의 총합) 보다 큰 것중에 가장 작은 값이 곧 답이 된다.

그러나, (u와v의 간선중 가장 큰 경로) == (w)

인경우를 생각 해보면 결국,

(기존 mst의 간선의 총합)-(u와v의 간선중 가장 큰 경로)+(w) == (기존 mst의 간선의 총합)

이 되어버리기 때문에, 실제로는 다른 mst가 존재함에도 불구하고 conitnue 하게 된다.

그렇기 때문에, 첫번째로 큰 간선이 w와 같은 경우에

두번째로 큰 간선을 찾아서 똑같이 적용시키면 된다.

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <cstring>
using namespace std;

#define MAX_N 50001
#define MAX_PAR 20
#define SWAP(a,b) {int t= b; b = a; a = t;}
typedef long long ll;

int par[MAX_N][MAX_PAR]; // 부모 배열
int MAX[MAX_N][MAX_PAR]; // 최댓값 배열
int depth[MAX_N]; // 깊이 배열
bool visit[MAX_N]; // DFS 체크

// 입력 순서대로 우선 저장될 edge 정보
class edge {
public:
     int u, v, w;
     edge() {}
     edge(int u, int v, int w) {
          this->u = u;
          this->v = v;
          this->w = w;
     }
};
vector<edge> edges; // 입력 순서대로 저장

// MST를 위한 간선
vector<pair<int, int>> map[MAX_N];

// PQ에 들어갈 아이템 ( cost 순으로 정렬 됨 )
class PQItem {
public:
     int now, nowDepth, prev, prevDist;
     PQItem() {}
     PQItem(int now, int nowDepth, int prev, int prevDist) {
          this->now = now;
          this->nowDepth = nowDepth;
          this->prev = prev;
          this->prevDist = prevDist;
     }
     bool operator < (const PQItem & b) const {
          return this->prevDist < b.prevDist;
     }
     bool operator > (const PQItem & b) const {
          return this->prevDist > b.prevDist;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

// 입력받을 V, E
int V, E;
ll MST() {
     int cnt = 0, ret = 0; 
     pq.push(PQItem(1, 0, 1, 0)); // 1번노드부터 pq push
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int now = top.now;
          int prev = top.prev;
          int prevDist = top.prevDist;
          int nowDepth = top.nowDepth;
          if (visit[now]) continue;
          par[now][0] = prev; // 1번째 부모
          MAX[now][0] = prevDist; // 부모와의 dist
          depth[now] = nowDepth; // 현재 depth
          ret += prevDist; // mst 간선의 총합을 위한 리턴값
          visit[now] = true; // visit 체크
          cnt++; // MST의 존재여부 파악을 위함
          for (int i = 0; i < map[now].size(); ++i) {
               if (!visit[map[now][i].first]) {
                    pq.push(PQItem(map[now][i].first, nowDepth + 1, now, map[now][i].second));
               }
          }
     }
     if (cnt != V) ret = -1; // mst가 존재하지않는다 ( = 한 정점에서 모든 정점을 방문 할 수 없다 )
     return ret;
}

// lca 알고리즘
int LCA(int x, int y) {
     if (depth[x] > depth[y]) SWAP(x, y);

     for (int i = 19; i >= 0; i--) {
          int diff = depth[y] - depth[x];
          if (diff >= (1 << i)) {
               y = par[y][i];
          }
     }
     if (x == y) return x;
     for (int i = 19; i >= 0; i--) {
          if (par[x][i] != par[y][i]) {
               x = par[x][i];
               y = par[y][i];
          }
     }
     return par[x][0];
}

// x노드와 y노드 사이의 간선의 최댓값 리턴
int getMax(int x, int y) {
     int lca = LCA(x, y);
     int ret = -1;
     int x_to_lca = depth[x] - depth[lca];
     int y_to_lca = depth[y] - depth[lca];
     for (int i = 19; i >= 0; i--) {
          if (x_to_lca >= (1 << i)) {
               ret = max(ret, MAX[x][i]);
               x_to_lca -= (1 << i);
               x = par[x][i];
          }
     }

     for (int i = 19; i >= 0; i--) {
          if (y_to_lca >= (1 << i)) {
               ret = max(ret, MAX[y][i]);
               y_to_lca -= (1 << i);
               y = par[y][i];
          }
     }
     return ret;
}

// x노드와 y 노드 사이의 2번째로 큰 ( prevMax보다 첫번째로 작은 ) 값 리턴
// O(N)으로 탐색했음 ( 더좋은 방법이 있을 것 같음 )
int getSecondMax(int x, int y, int prevMax) {
     int lca = LCA(x, y);
     int x_to_lca = depth[x] - depth[lca];
     int y_to_lca = depth[y] - depth[lca];
     int ret = -1;
     for (int i = 0; i < x_to_lca; ++i) {
          if (MAX[x][0] < prevMax) {
               ret = max(ret, MAX[x][0]);
          }
          x = par[x][0];
     }

     for (int i = 0; i < y_to_lca; ++i) {
          if (MAX[y][0] < prevMax) {
               ret = max(ret, MAX[y][0]);
          }
          y = par[y][0];
     }
     return ret;
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0); cout.tie(0);
     cin >> V >> E;
     for (int i = 0; i < E; ++i) {
          int a, b, w; cin >> a >> b >> w;
          edges.push_back(edge(a, b, w));
          map[a].push_back({ b,w });
          map[b].push_back({ a,w });
     }

     ll minimum = MST();
     if (minimum == -1) {
          cout << -1 << "\n";
          return 0;
     }

     for (int i = 1; i <= 19; ++i) {
          for (int j = 1; j <= V; j++) {
               par[j][i] = par[par[j][i - 1]][i - 1];
               MAX[j][i] = max(MAX[j][i - 1], MAX[par[j][i - 1]][i - 1]);
          }
     }

     int ans = INT_MAX;
     for (int i = 0; i < E; ++i) {
          int u, v, w;
          u = edges[i].u;
          v = edges[i].v;
          w = edges[i].w;
          int maxE = getMax(u, v);
          // 가장 큰 값과 비교
          if (minimum - maxE + w > minimum) {
               if (ans > minimum - maxE + w) ans = minimum - maxE + w;
          }
          // 가장 큰 값이 현재 삽입하려는 간선의 weight와 같다면
          // 두번 째로 큰 간선을 찾는다
          else if (minimum - maxE + w == minimum) {
               int secondMaxE = getSecondMax(u, v, maxE);
               // 찾았 다면
               if (secondMaxE != -1) {
                    if (ans > minimum - secondMaxE + w) ans = minimum - secondMaxE + w;
               }
          }
     }
     if (ans == INT_MAX) cout << -1 << "\n";
     else cout << ans << "\n";
}