일반적으로 미니멈 스패닝 트리는 가중치 총합을 최소로 줄이는 건데
내가 책에서 본 문제는 가중치 중 제일 큰거를 최대한 작게 하는 스패닝트리임
코드는 짰는데 문제로 검증을 하고싶음
1. 그걸 구하는 문제 있음?
2. 간선 가중치가 다이나믹하게 늘거나 줄때 쿼리형식으로 구하는 문제 있음?
MST태그로 찾고있는데 다 MST만나와서 못찾겠음
내가 책에서 본 문제는 가중치 중 제일 큰거를 최대한 작게 하는 스패닝트리임
코드는 짰는데 문제로 검증을 하고싶음
1. 그걸 구하는 문제 있음?
2. 간선 가중치가 다이나믹하게 늘거나 줄때 쿼리형식으로 구하는 문제 있음?
MST태그로 찾고있는데 다 MST만나와서 못찾겠음
https://www.acmicpc.net/problem/7148
그나마 이게 제일 가까워보이긴 하네
다이나믹 mst 존나어려운거아니냐 - dc App
링크컷쓰는 - dc App
그래프가 클때 최적화기법이 링크컷이고 그래프가 중간 크기면 링크컷까진 안써도됨
간선 가중치 바뀌면 링컷 의미 없다 링컷으로 풀려면 offline dynamic connectivity도 써서 amortized O(qlog^2n)이 될텐데 그거 쓸거면 차라리 offline dynamic mst가 더 나음 O(qlog^2n)
근데 가장 큰게 최대한 작은거면 걍 mst인데 크루스칼 잘 생각해봐
https://en.m.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree
이걸 MBST라 하는데 MST는 MBST인데 MBST는 꼭 MST일 필요는 없음. MBST는 O(E)에 구할 수 있음
다이나믹 아니면 가장 큰 간선의 가중치 값으로 이분탐색 하면 됨