14955번: How Many to Be Happy?

14955번: How Many to Be Happy? - 최소 컷

N개의 정점과 M개의 간선으로 이루어진 그래프에서 각 간선이 MST가 포함되기 위해

제거해야하는 간선의 최소 개수의 합을 구하는 문제이다.

접근 방법은 다음과 같다.

u와 v를 잇는 가중치가 c인 간선이 있을 때 이 때 이 간선이 MST가 아니라는 것은

가중치가 c미만인 간선들로 u와 v가 이어져 있다는 것이다.

이제 이 간선을 MST에 포함되게 하려면 가중치가 c미만인 간선들로 u와 v가 이어져있지 않게 해야한다는 뜻이 되며

이는 각각의 간선을 용량이 1인 간선으로 보았을 때

가장 작은 유량으로 u와 v가 각각 다른 집합에 속하도록 나누는, 즉 최소 컷을 구하는 문제가 된다.

매 간선을 보며 그 간선의 비용보다 작은 간선으로만 용량이 1인 간선으로 이어 그래프를 만들어 준 뒤,

u를 싱크, v를 소스로 하는 최소 컷을 구하여 합을 구해주면 풀 수 있는 문제이다.