8063 : 최대 유량
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 노드와 노드들을 연결하는 $M$개의 단방향 연결 통로가 주어집니다.
각 연결 통로는 보낼 수 있는 데이터 양의 한계치인 용량(Capacity)을 가지고 있습니다.
$1$번 노드(소스)에서 $N$번 노드(싱크)로 한 번에 전송할 수 있는 최대 데이터 유량(Max Flow)을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 300$
• $1 \le M \le 1{,}000$
• $1 \le u, v \le N$ ($u \neq v$)
• $1 \le c \le 10^9$
각 연결 통로는 보낼 수 있는 데이터 양의 한계치인 용량(Capacity)을 가지고 있습니다.
$1$번 노드(소스)에서 $N$번 노드(싱크)로 한 번에 전송할 수 있는 최대 데이터 유량(Max Flow)을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 300$
• $1 \le M \le 1{,}000$
• $1 \le u, v \le N$ ($u \neq v$)
• $1 \le c \le 10^9$
입력 설명
첫째 줄에 노드의 개수 $N$과 연결 통로의 개수 $M$이 공백으로 구분되어 주어집니다. ($2 \le N \le 300$, $1 \le M \le 1{,}000$)
둘째 줄부터 $M$개의 줄에 걸쳐 통로의 시작 노드 $u$, 도착 노드 $v$, 그리고 용량 $c$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$, $u \neq v$, $1 \le c \le 10^9$)
둘째 줄부터 $M$개의 줄에 걸쳐 통로의 시작 노드 $u$, 도착 노드 $v$, 그리고 용량 $c$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$, $u \neq v$, $1 \le c \le 10^9$)
출력 설명
$1$번 노드에서 $N$번 노드로 보낼 수 있는 최대 유량을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1 2 5
1 3 4
2 3 3
2 4 2
3 4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
에드몬즈-카프(Edmonds-Karp) 알고리즘 또는 디닉(Dinic) 알고리즘을 구현하여 최대 유량을 탐색합니다.
용량 $c$가 최대 $10^9$으로 매우 크기 때문에 유량 증가 경로를 찾을 때마다 용량을 업데이트해야 합니다.
용량 $c$가 최대 $10^9$으로 매우 크기 때문에 유량 증가 경로를 찾을 때마다 용량을 업데이트해야 합니다.