네트워크 최소 절단
다이아몬드 III의견: 0
\(N\)개의 정점과 \(M\)개의 가중치 있는 무방향 간선으로 이루어진 그래프가 주어진다. 간선의 가중치는 양의 정수이며, 같은 정점 쌍 사이에 여러 간선이 존재할 수 있다.
정점 집합을 공집합이 아닌 두 부분 \(S\)와 \(V \setminus S\)로 나눌 때, 한쪽 끝은 \(S\)에 다른 끝은 \(V \setminus S\)에 속하는 간선들의 가중치 합을 그 분할의 절단값이라 한다. 가능한 모든 분할 중 절단값의 최솟값(전역 최소 절단, global minimum cut)을 구하여라.
특정한 두 정점을 분리하는 것이 아니라 임의의 분할을 허용하므로 최대 유량을 매번 계산하는 것은 비효율적이다.
\(2 \le N \le 500\)
\(1 \le M \le 100{,}000\)
\(1 \le u, v \le N\), \(u \ne v\)
\(1 \le c \le 10^4\)
첫 줄에 정점 수 \(N\)과 간선 수 \(M\)이 주어진다. 정점은 \(1\)부터 \(N\)까지 번호가 매겨져 있다.
다음 \(M\)개의 줄에 각각 세 정수 \(u\), \(v\), \(c\)가 주어지며, 이는 정점 \(u\)와 \(v\)를 잇는 가중치 \(c\)의 간선을 의미한다.
전역 최소 절단값을 한 줄에 출력한다.
4 5
1 2 2
2 3 3
3 4 4
4 1 1
1 3 5
5간선은 \((1,2)=2,(2,3)=3,(3,4)=4,(4,1)=1,(1,3)=5\)이다. 정점 \(\{4\}\)를 따로 떼면 간선 \((3,4)=4\)와 \((4,1)=1\)이 잘려 절단값 \(5\)이다. 다른 어떤 분할도 이보다 작은 절단값을 만들 수 없으므로 전역 최소 절단값은 \(5\)이다.
6 7
1 2 5
2 3 5
1 3 5
4 5 5
5 6 5
4 6 5
3 4 1
1두 개의 삼각형(각 변 무게 \(5\))이 무게 \(1\)짜리 다리 하나로 연결되어 있다. 이 다리만 끊으면 그래프가 둘로 나뉘므로 최소 절단값은 \(1\)이다.
플래티넘 IIIriseoj 작성
출처 Original
평가 및 의견
네트워크 최소 절단
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
네트워크 최소 절단