6225 : 최소 컷
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
소스 S에서 싱크 T로의 최소 컷 용량과 소스 컴포넌트 노드 목록을 구하시오.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E (1 ≤ N ≤ 1,000, 1 ≤ E ≤ 10,000), 소스 S와 싱크 T가 주어집니다.
E개의 줄에 간선 정보 u, v, capacity가 주어집니다.
E개의 줄에 간선 정보 u, v, capacity가 주어집니다.
출력 설명
첫째 줄에 최소 컷의 용량 합을 출력하고, 둘째 줄에 소스 컴포넌트에 속한 노드 번호를 오름차순으로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5 1 4
1 2 3
1 3 2
2 4 2
3 4 3
2 3 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1