글 읽기 - 스패닝 트리 응용 문제를 어떻게 풀어야할까요?

filot 7년 전 0

N 개의 정점이 있습니다. 간선은 당연히 최대 N-1 이겠죠

근데 이걸 스패링 트리를 구성을 해야하는데 특이하게 최소의 비용이 아니라

구성된 스패닝 트리 중에서 간선의 최대값과 최소값의 차이가 최소가 되게 해야합니다.

근데 이걸 스패닝 알고리즘으로 안풀릴듯하고

DP를 이용한 TSP의 응용 같기도한데 어떻게 계속 최대값과 최소값의 차이가 적게 나도록 유지를 할지도 어렵네요

혹시 도움이 될만한 자료가 있을까요?

O(M^2)이라면 최소 비용 스패닝 트리와 최대값을 최소로 하는 스패닝 트리가 같기 때문에 구할 수 있고,
O(MN) 이나 O(N^2)이라면 위의 내용에서 추가로 생각을 더 해봐야겠네요.
O(M lg^2 M) 풀이를 원하신다면 https://en.wikipedia.org/wiki/Dynamic_connectivity#Fully_dynamic_connectivity

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스패닝 트리 응용 문제를 어떻게 풀어야할까요?

filot 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말