hellogaon

14955번: How Many to Be Happy? - 최소 컷 N개의 정점과 M개의 간선으로 이루어진 그래프에서 각 간선이 MST가 포함되기 위해제거해야하는 간선의 최소 개수의 합을 구하는 문제이다. 접근 방법은 다음과 같다.u와 v를 잇는 가중치가 c인 간선이 있을 때 이 때 이 간선이 MST가 아니라는 것은가중치가 c미만인 간선들로 u와 v가 이어져 있다는 것이다.이제 이 간선을 MST에 포함되게 하려면 가중치가 c미만인 간선들로 u와 v가 이어져있지 않게 해야한다는 뜻이 되며이는 각각의 간선을 용량이 1인 간선으로 보았을 때가장 작은 유량으로 u와 v가 각각 다른 집합에 속하도록 나누는, 즉 최소 컷을 구하는 문제가 된다. 매 간선을 보며 그 간선의 비용보다 작은 간선으로만 용량이 1인 간선으로..

최소 컷(Minimum Cut)은 민 컷이라고도 불리며 네트워크에서 용량이 가장 작은 컷을 말합니다.이 때 컷이란 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점을 두 개의 집합으로 나눈 것으로소스가 속한 집합을 S, 싱크가 속한 집합을 T라 할 때S에서 T로 가는 간선들의 용량 합을 컷의 용량, 유량 합을 컷의 유량이라고 합니다.컷은 아래와 같이 2가지의 속성은 만족합니다. 1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다.2. 컷의 유량은 용량과 같거나 더 작다. 이 때 최소 컷 최대 유량 정리(Max-Flow Min-Cut Theorem)에 의하여최소 컷은 네트워크 유량 문제에서의 최대 유량과 동일하다는 것을 이용하여 문제를 풀 수 있습니다.네트워크 그래프에서 최소 용량의 간선을 자르고..