블로그 이사 중입니다 >> gumgood.github.io

C++11 절약할 수 있는 액수는 가로등을 최소로 살려놓았을 때 최대가 된다. 최소 스패닝 트리를 찾아 전체 액수에서 빼준다.

무방향성 가중치 그래프 G에 대해- Spanning tree : 그래프 G의 모든 node를 포함하는 Tree를 말한다. 그래프 G의 부분그래프- MST(Minimum Spanning Tree) : G에 대한 spanning tree 중 가중치의 합이 가장 작은 tree MST를 찾는 Greedy method가 있다. (Prim, Kruskal, Sollin...)대표적인 Kruskal's algorithm에 대해서만 서술한다. 1. Kruskal's algorithm 수행과정 ① graph의 모든 edge를 가중치의 오름차순으로 정렬한다. ② edge의 가중치가 작은 순으로 spanning tree에 추가해나간다. ③ 추가했을 때 spanning tree와 cycle이 생기는 간선은 제외한다. ④ ②~..