백준 1626번 두 번째로 작은 스패닝 트리
문제
방향성이 없는 그래프 G가 주어진다. 문제는 G의 최소 스패닝 트리보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.
MST와 second MST의 모습
문제풀이
사용한 알고리즘: MST, LCA두번째로 작은 스패닝트리 (이하 SST) 를 찾는 문제였습니다.
SST는 MST보다 커야 합니다. (같으면 안됩니다.)
이 문제는 많이 까다로운 문제로 집중해서 읽어주세요....
( 정리한다고 정리했는데.... 제 생각이 정확히 전달 되는 글이었으면 좋겠습니다. )
(0) 생각
우선 MST 를 만들고, MST 만드는데 사용되지 않은 간선들을 저장합니다.SST 를 만들기 위해서는 쓰지 않은 간선 중 하나를 MST 에 추가하고,
기존 MST 간선 중 하나를 제거해야 하는 것을 생각할 수 있습니다.
a, b 노드를 연결하는 쓰지않은 간선을 추가하는 경우,
a, b 노드를 연결하는 쓰지않은 간선을 추가하는 경우,
해당 간선부터 a, b 의 최소공통조상까지 cycle이 발생함을 알 수 있습니다.
다시 말해 a, b 노드의 공통 조상까지 연결된 간선들 중 하나를 제거하면 됩니다.
제거해야 하는 기존 간선은 cycle 안의 간선 중 가장 큰 간선 이며
제거해야 하는 기존 간선은 cycle 안의 간선 중 가장 큰 간선 이며
추가되는 간선과 값이 같아서는 안된다 를 생각할 수 있습니다.
( 값이 같을 경우 새로생긴 ST값 = MST 값 이 됩니다. SST는 MST와 같으면 안됩니다. )
쓰지 않은 모든 간선들을 넣어보고, 위 방법을 통해 기존 간선 하나를 빼보며 스패닝트리(이하ST) 를 만들어 봅니다. 이때 만들어지는 ST 값은 MST 값보다 크거나 같을 것입니다.
위 과정으로 만들어지는 ST 중 MST 값보다 최소로 큰 ST 가 SST입니다.
이때 MST 구성에 쓰인지 여부를 판단하기위해 bool을 하나 만들어줍니다.
'parent[i][k] : i노드의 2^k번째 조상' 이라 설정하고 구해주었습니다.
'Biggest[i][k] : i노드의 2^k번째 조상까지 갈 때까지 <가장 큰 간선, 두번째로 큰 간선>' 이라 설정하고 이를 구해줬습니다.
쓰지 않은 간선이 들어오면, 제거할 기존 간선을 미리 구해 놓은 것입니다.
( '추가되는 쓰지 않은 간선' 과 '제거할 가장 큰 기존 간선' 의 값이 같을 경우를 대비해 두번째로 큰 간선을 구해두었습니다.)
적절한 간선이란, 쓰지 않은 간선이 추가될 때 만들어지는 cycle 안의 기존간선 중 가장 크면서 쓰지 않은 간선과 같지 않은 기존간선입니다.
과정(6)에서 미리 만들어 놓은 Biggest[i][k] 를 통해 적절한 간선을 찾습니다.
( 값이 같을 경우 새로생긴 ST값 = MST 값 이 됩니다. SST는 MST와 같으면 안됩니다. )
쓰지 않은 모든 간선들을 넣어보고, 위 방법을 통해 기존 간선 하나를 빼보며 스패닝트리(이하ST) 를 만들어 봅니다. 이때 만들어지는 ST 값은 MST 값보다 크거나 같을 것입니다.
위 과정으로 만들어지는 ST 중 MST 값보다 최소로 큰 ST 가 SST입니다.
(1) 코드 147~151
문제 첫줄에 MST가 존재한다고 명시 했으나 출력 조건에는 MST가 존재하지 않는다면 -1 출력이라고 나와있습니다... 실제로 MST 가 존재하지 않는 TC가 주어집니다.(2) 코드 10~18
입력받는 모든 간선들을 struct로 저장해줍니다.이때 MST 구성에 쓰인지 여부를 판단하기위해 bool을 하나 만들어줍니다.
(3) 코드 19~37, 122~143
MST 를 만들어줍니다.(4) 코드 39~40, 138~140
만들어진 MST로 LCA 돌리기 위해, 과정(4) 에서 MST 만들 때 노드들의 부모-자식 관계를 간선 가중치와 함께 저장해 둡니다.(5) 코드 42~60, 149~179
LCA 를 돌리기 위해 1을 root로 잡고 MST 의 노드들의 깊이를 정해줍니다.'parent[i][k] : i노드의 2^k번째 조상' 이라 설정하고 구해주었습니다.
'Biggest[i][k] : i노드의 2^k번째 조상까지 갈 때까지 <가장 큰 간선, 두번째로 큰 간선>' 이라 설정하고 이를 구해줬습니다.
쓰지 않은 간선이 들어오면, 제거할 기존 간선을 미리 구해 놓은 것입니다.
( '추가되는 쓰지 않은 간선' 과 '제거할 가장 큰 기존 간선' 의 값이 같을 경우를 대비해 두번째로 큰 간선을 구해두었습니다.)
(6) 코드 61~113,180~188
쓰지 않은 간선들을 하나씩 넣고, 기존 MST 간선 중 적절한 간선을 찾아 제거해봅니다.적절한 간선이란, 쓰지 않은 간선이 추가될 때 만들어지는 cycle 안의 기존간선 중 가장 크면서 쓰지 않은 간선과 같지 않은 기존간선입니다.
과정(6)에서 미리 만들어 놓은 Biggest[i][k] 를 통해 적절한 간선을 찾습니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAX = 50000; | |
| // 2^16 > 50000 | |
| const int DMAX = 16; | |
| const int INF = INT_MAX; | |
| typedef pair<int, int> pii; | |
| int V, E; | |
| // 점 A, 점 B 연결하는 Edge , 가중치는 W | |
| struct Edge{ | |
| int A; | |
| int B; | |
| int W; | |
| bool Used = false; | |
| Edge():Edge(0,0,0){} | |
| Edge(int a1, int b1, int w1): A(a1), B(b1), W(w1){} | |
| }; | |
| // Edge 들 저장 | |
| vector<Edge> Vec; | |
| // 가중치 W 작은거부터 | |
| bool cmp(const Edge &E1, const Edge &E2){ | |
| return E1.W < E2.W; | |
| } | |
| // Union Find | |
| // R[i] : i의 root | |
| int R[MAX+1]; | |
| int Find(int x){ | |
| if(R[x]==0) return x; | |
| return R[x] = Find(R[x]); | |
| } | |
| void Union(int x, int y){ | |
| int xRoot = Find(x); | |
| int yRoot = Find(y); | |
| if(xRoot == yRoot) return; | |
| R[yRoot] = xRoot; | |
| } | |
| //LCA 를 위한 재료 | |
| // adj[i] : < i 의 자식노드 , 해당 가중치 > | |
| vector<pii> adj[MAX+1]; | |
| int Depth[MAX+1]; | |
| // parent[i][k] = i의 2^k 조상 | |
| int parent[MAX+1][DMAX+1]; | |
| // Biggest[i][k] : i의 2^k 조상으로 가는 길에 있는 <가장 큰 간선 , 2번째로 큰 간선> | |
| // 가장큰간선 != 2번째로큰간선 으로 만들어준다. | |
| // -> 모든 edge 의 가중치가 1 인 경우 등의 예외 방지 | |
| // 쓰이지 않은 간선 추가시 가장 큰 간선으로 대체 했을 경우 | |
| pii Biggest[MAX+1][DMAX+1]; | |
| // i 들의 depth 구성 | |
| void MakeDepth(int curr){ | |
| for(auto child: adj[curr]){ | |
| if(Depth[child.first]!=0) continue; | |
| Depth[child.first] = Depth[curr]+1; | |
| parent[child.first][0] = curr; | |
| // MST 를 구성하는 edge 들의 최소값을 계산하면서 갈꺼다. (코드 52~54) | |
| Biggest[child.first][0] = pii(child.second,-1); | |
| MakeDepth(child.first); | |
| } | |
| } | |
| // 추가할 Edge(a~b) 가 만드는 cycle 을 LCA 를 이용해 찾고, cycle 안에 대체 가능한 가장 큰 수 찾기 | |
| int HowAboutThis(Edge EE){ | |
| int x = EE.A; | |
| int y = EE.B; | |
| int w = EE.W; | |
| // 대체가능한 간선의 가장 큰 가중치. w 와 달라야한다. | |
| int ret = -1; | |
| if(Depth[x]<Depth[y]) swap(x,y); | |
| int diff = Depth[x] - Depth[y]; | |
| int cnt = 0; | |
| while(diff){ | |
| if(diff%2==1){ | |
| //경로중 가장 큰 가중치 | |
| if(Biggest[x][cnt].first!=w) | |
| ret = max(ret, Biggest[x][cnt].first); | |
| //경로중 두번째 큰 가중치 | |
| else if(Biggest[x][cnt].second!=-1) | |
| ret = max(ret, Biggest[x][cnt].second); | |
| x = parent[x][cnt]; | |
| } | |
| diff/=2; | |
| cnt++; | |
| } | |
| if(x!=y){ | |
| for (int i = DMAX; i >= 0; i--){ | |
| if(parent[x][i]!=parent[y][i]){ | |
| if(Biggest[x][i].first!=w) | |
| ret = max(ret, Biggest[x][i].first); | |
| else if(Biggest[x][i].second!=-1) | |
| ret = max(ret, Biggest[x][i].second); | |
| if(Biggest[y][i].first!=w) | |
| ret = max(ret, Biggest[y][i].first); | |
| else if(Biggest[y][i].second!=-1) | |
| ret = max(ret, Biggest[y][i].second); | |
| x = parent[x][i]; | |
| y = parent[y][i]; | |
| } | |
| } | |
| if(Biggest[x][0].first!=w) | |
| ret = max(ret, Biggest[x][0].first); | |
| else if(Biggest[x][0].second!=-1) | |
| ret = max(ret, Biggest[x][0].second); | |
| if(Biggest[y][0].first!=w) | |
| ret = max(ret, Biggest[y][0].first); | |
| else if(Biggest[y][0].second!=-1) | |
| ret = max(ret, Biggest[y][0].second); | |
| x = parent[x][0]; | |
| } | |
| return ret; | |
| } | |
| int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); | |
| cin >> V >> E; | |
| for(int i=0; i<E; ++i){ | |
| int a, b, w; | |
| cin >> a >> b >> w; | |
| Vec.push_back(Edge(a,b,w)); | |
| } | |
| // 최소 스패닝 트리 만드는 간선비용 | |
| int MST = 0; | |
| // V-1 개의 Edge 나오면 MST 완성! | |
| int cnt = 0; | |
| // 가중치 작은순 | |
| sort(Vec.begin(), Vec.end(), cmp); | |
| // MST | |
| for(int i=0; i<E; ++i){ | |
| int a = Vec[i].A; | |
| int b = Vec[i].B; | |
| int aRoot = Find(a); | |
| int bRoot = Find(b); | |
| if(aRoot == bRoot) continue; | |
| Union(a,b); | |
| MST += Vec[i].W; | |
| Vec[i].Used = true; | |
| // LCA 돌리기 위해 자식 저장 | |
| adj[a].push_back(pii(b,Vec[i].W)); | |
| adj[b].push_back(pii(a,Vec[i].W)); | |
| cnt++; | |
| if(cnt==V-1) break; | |
| } | |
| // MST 가 애초에 없는 경우 | |
| if(cnt!=V-1 || E<=V-1){ | |
| cout << -1 << '\n'; | |
| return 0; | |
| } | |
| // LCA 구현, 1번 노드를 Root로 생각 | |
| Depth[1] = 1; | |
| // tree Depth 만들기 | |
| MakeDepth(1); | |
| for (int k = 0; k <= DMAX; ++k){ | |
| for (int i = 1; i <= V; ++i){ | |
| int Father = parent[i][k]; | |
| if(Father && parent[Father][k]!=0){ | |
| // i가 2^k 조상 갈때 큰 가중치 2개 , < w1, w2 > (w1>w2) | |
| int w1 = Biggest[i][k].first; | |
| int w2 = Biggest[i][k].second; | |
| // father이 2^k 조상 갈때 큰 가중치 2개 , < f1, f2 > (f1>f2) | |
| int f1 = Biggest[Father][k].first; | |
| int f2 = Biggest[Father][k].second; | |
| // 큰 가중치 정하기 | |
| if(w1>f1){ | |
| Biggest[i][k+1].first = w1; | |
| Biggest[i][k+1].second = max(f1,w2); | |
| } | |
| else if(w1<f1){ | |
| Biggest[i][k+1].first = f1; | |
| Biggest[i][k+1].second = max(w1,f2); | |
| } | |
| // w1==f1이면 | |
| else | |
| Biggest[i][k+1] = pii(w1,max(w2,f2)); | |
| parent[i][k+1] = parent[Father][k]; | |
| } | |
| } | |
| } | |
| // 안써본 Edge 써서 MST 바로 밑 값 구해보기! (2번째 MST) | |
| int Plus = INF; | |
| for(int i=0; i<E; ++i){ | |
| // MST 만들 때 사용한 간선이면 패스 | |
| if(Vec[i].Used) continue; | |
| int t = HowAboutThis(Vec[i]); | |
| if(t==-1 || t==Vec[i].W) continue; | |
| Plus = min(Plus, Vec[i].W-t); | |
| } | |
| if(Plus==INF) cout << -1 << '\n'; | |
| else cout << MST+Plus << '\n'; | |
| return 0; | |
| } |
댓글
댓글 쓰기
긴 글 읽어주셔서 감사합니다.
궁금한게 있으시다면 댓글 달아주세요!