Monday, June 29, 2015

JAG Spring Contest 2013 E번 / KOI 2014 고등부 4번


주어진 그래프에서 MST G(m)이 있다고 하자.

G(m)에 포함되지 않은 간선을 자르는 경우에만 Gi가 현재 MST의 weight sum(=S)과는 다른 값을 가지게 된다. i번째 간선을 자르면 G(m)은 이분 그래프가 되는데, 이 때 두 subgraph를 연결하는 가장 작은 간선을 골라주면 되는 것이다.

Kruskal Algorithm을 기반으로 MST를 구성했다고 가정하자.
MST에 포함되지 않는 간선들을 가중치 순으로 Union-Find 처리해주면서 depth가 서로 다른 두 정점 u, v(dfs tree에서 depth(u) > depth(v))가 있다면, Gi('u와 u의 부모' 간선 index) = S - ('u와 u의 부모' 간선의 가중치) + (현재 i번째 간선의 가중치)를 대입하는 과정을 u와 v가 다를 때까지 반복해주면 된다.
Kruskal Algorithm 원리 특성상 만약 지금 i번째 간선이 MST의 간선이면, i번째 간선(u,v)를 제외했을 때 그 간선의 정점 u, v가 같은 Union이 되기 위해서는 j>i인 j번째 간선이 필수적으로 필요하기 때문에 역으로 처리해준다고 보면 이해하기가 더 쉬울 수 있겠다.

소스 코드(Source Code)

No comments:

Post a Comment