6186 : 트리 최소컷
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치가 있는 트리와 소스 S, 싱크 T가 주어집니다. S와 T를 분리하기 위해 트리 상에서 가중치 합이 최소가 되도록 간선들을 끊으려고 합니다. 이때 제거해야 하는 간선들의 가중치 합의 최솟값을 구하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 1,000)과 소스 S, 싱크 T (1 ≤ S, T ≤ N, S ≠ T)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v, w가 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v, w가 주어집니다.
출력 설명
S와 T를 분리하기 위한 최소 컷 용량(간선 가중치 합의 최솟값)을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4 5
1 2 5
1 3 2
3 4 8
3 5 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3