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

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

두 번째로 작은 스패닝 트리 

방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다. 문제는 최소 스패닝 트리 T보다는 크면서 가장 작은 스패닝 트리인

 'The second minimum spanning tree'를 구하는 것이다.

MST와 second MST의 모습

입력

첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 

그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다.

출력

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

예제 입력 

7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26

예제 출력 

44

---

먼저 생각해 볼 수 있는건, kruskal algorithm을 통해 MST를 만들고 만들어진 MST에서 간선을 하나 제거하고 다른 Spanning Tree를 만들고를 반복해보면 2nd MST를 만들 수 있다. MST를 만들 때 간선이 V-1개 필요했으니, V-1개를 각각 한번씩 제거하면서 새로운 Spanning Tree를 만드므로 시간복잡도는 O(VE)정도 되려나? 당연히 TLE..

다르게 생각해 볼 수 있는 방법은 만들어진 MST에서 간선을 먼저 제거하지말고 MST를 구성하지 않는 간선중에 임의의 간선을 추가해 본다. MST를 구성하지 않는 모든 간선에 대해 이 작업을 반복.. 총 E-(V-1)번 반복한다.

하나의 간선을 추가하면 N개의 정점에 N개의 간선이 연결되어 있으므로 당연히 하나의 cycle이 생기게 될텐데 잘 생각해보면 이 사이클을 이루는 간선 중 아무거나 하나의 간선을 제거하면 Spanning Tree가 됨을 알 수 있다. 따라서 2nd MST를 만들기 위해선 cycle을 이루는 간선 중 (적어도) 가장 큰 간선을 제거해야 함을 알 수 있다. cycle을 이루는 모든 간선을 하나씩 살피면서 max값을 찾는다면 이 역시 O(V)이므로, 총 시간복잡도는 O(VE)로 시간초과. 시간을 줄이기 위해 LCA를 구할 때 사용하는 sparse table을 구성하는 방법이 있다. 

먼저 새로 연결된 두 노드의 LCA찾으면 그 지점이 cycle을 이루는 부모가 됨을 알 수 있다. 단, 이 cycle에서 가장 가중치가 큰 간선을 제거하는 것이 2nd MST의 후보가 되므로 LCA를 구할 때 부모노드의 sparse table을 구성하는 것 처럼, 구간 내에 최대 간선의 값을 저장하는 sparse table을 같이 구성하면 log시간복잡도로 처리가 가능하다.

sparse[i][j] : i번노드에서 거리가 2^j만큼 있는 부모노드 사이의 최대 간선 가중치, sparse[i][j+1] = max(sparse[i][j], sparse[lca[i][j]][j]) 정도로 값을 업데이트 해줄 수 있다.

다만 또 생각해 봐야하는것이; 만약 가장 큰 간선을 제거했는데, 총 가중치가 MST와 같다면. 즉, 새로 추가한 간선과 제거한 간선의 가중치가 같다면 그 tree는 2nd MST가 아닌 1st MST이다. 따라서 두번째로 큰 간선의 가중치를 가지는 sparse table을 하나 더 만들어, 만약 가장 큰 간선의 가중치가 새로 추가한 간선의 가중치가 같다면 두번쨰로 큰 간선의 가중치를 빼주는 식으로 문제를 해결해야 한다. (혹은 새로 연결한 간선보다 작은 가중치를 가지는 간선중에 최대 값을 가지는 sparse table 하나만 구성해도 된다.)

시간복잡도는 ElogE(kruskal) + ElogE(LCA) = O(ElogE)이다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAXN 50004
#define MAXM 200004
#define MAXX (int)1e8
using namespace std;
vector <pair <int, pair <int, int>>> v;
vector<pair<int, int>> vv[MAXN];
int r[MAXN], rr[MAXN][17], val[MAXN][17], val2[MAXN][17], depth[MAXN], stk[MAXN], visited[MAXN], used[MAXM];
int n, m, a, b, c, now1, now2;
int min_d, second_d, ans;
int father(int x) {
	if (r[x] == x) return x;
	return r[x] = father(r[x]);
}
void join(int x, int y) {
	r[father(x)] = father(y);
}
__inline int max(int a, int b) {
	return a > b ? a : b;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		v.push_back({ c,{ a,b } });
	}
	sort(v.begin(), v.end());
	for (int j = 1; j <= n; j++) r[j] = j;
	int cnt = 0;
	//kruskal
	for (int j = 0; j < v.size() && cnt < n - 1; j++) {
		if (father(v[j].second.first) != father(v[j].second.second)) {
			join(v[j].second.first, v[j].second.second);
			vv[v[j].second.first].push_back({ v[j].second.second,v[j].first });
			vv[v[j].second.second].push_back({ v[j].second.first,v[j].first });
			cnt++;
			min_d += v[j].first;
			used[j] = 1;
		}
	}
	ans = MAXX;
	if (cnt == n - 1) {
		//make a tree
		for (int i = 1; i <= n; i++) {
			if (vv[i].size()) {
				int idx = 0;
				depth[i] = 0;
				stk[idx++] = i;
				visited[i] = 1;
				while (idx) {
					int now = stk[--idx];
					for (auto it : vv[now]) {
						if (visited[it.first]) continue;
						visited[it.first] = 1;
						stk[idx++] = it.first;
						depth[it.first] = depth[now] + 1;
						rr[it.first][0] = now;
						val[it.first][0] = it.second;
						for (int k = 1; (1 << k) <= depth[it.first]; k++) {
							rr[it.first][k] = rr[rr[it.first][k - 1]][k - 1];
							if (val[it.first][k - 1] > val[rr[it.first][k - 1]][k - 1]) {
								val[it.first][k] = val[it.first][k - 1];
								val2[it.first][k] = max(val2[it.first][k - 1], val[rr[it.first][k - 1]][k - 1]);
							}
							else if (val[it.first][k - 1] < val[rr[it.first][k - 1]][k - 1]) {
								val[it.first][k] = val[rr[it.first][k - 1]][k - 1];
								val2[it.first][k] = max(val[it.first][k - 1], val2[rr[it.first][k - 1]][k - 1]);
							}
							else {
								val[it.first][k] = val[it.first][k - 1];
								val2[it.first][k] = max(val2[it.first][k - 1], val2[rr[it.first][k - 1]][k - 1]);
							}
						}
					}
				}
				break;
			}
		}
		for (int j = 0; j < v.size(); j++) {
			if (used[j]) continue;
			now1 = v[j].second.first;
			now2 = v[j].second.second;
			int cand = -1;
			//lca
			if (depth[now1] > depth[now2]) {
				int diff = depth[now1] - depth[now2];
				while (diff) {
					int k = 0;
					while (diff >= (1 << (k + 1))) { k++; }
					if (val[now1][k] > cand && val[now1][k] != v[j].first) cand = val[now1][k];
					else if (val2[now1][k] > cand && val2[now1][k] != v[j].first) cand = val2[now1][k];
					now1 = rr[now1][k];
					diff = depth[now1] - depth[now2];
				}
			}
			else if (depth[now1] < depth[now2]) {
				int diff = depth[now2] - depth[now1];
				while (diff) {
					int k = 0;
					while (diff >= (1 << (k + 1))) { k++; }
					if (val[now2][k] > cand && val[now2][k] != v[j].first) cand = val[now2][k];
					else if (val2[now2][k] > cand && val2[now2][k] != v[j].first) cand = val2[now2][k];
					now2 = rr[now2][k];
					diff = depth[now2] - depth[now1];
				}
			}
			int k;
			while (now1 != now2) {
				k = 0;
				while (rr[now1][k + 1] != rr[now2][k + 1]) { k++; }
				if (val[now1][k] > cand && val[now1][k]!=v[j].first) cand = val[now1][k];
				else if (val2[now1][k] > cand && val2[now1][k] != v[j].first) cand = val2[now1][k];
				if (val[now2][k] > cand && val[now2][k] != v[j].first) cand = val[now2][k];
				else if (val2[now2][k] > cand && val2[now2][k] != v[j].first) cand = val2[now2][k];
				now1 = rr[now1][k];
				now2 = rr[now2][k];
			}
			if (cand==-1) continue;
			second_d = min_d - cand + v[j].first;
			if (ans > second_d) ans = second_d;
		}
	}
	printf("%d", ans == MAXX ? -1 : ans);
}