Loading...
$N$개의 정점과 $E$개의 단방향 간선으로 이루어진 네트워크가 주어진다. 각 간선은 보낼 수 있는 최대 유량과 유량 1당 발생하는 비용을 가진다. 정점 1에서 정점 $N$까지 보낼 수 있는 최대 유량과, 최대 유량을 흘릴 때 발생하는 최소 비용을 구하라.
여러 경로를 통해 유량을 흘릴 수 있으며, 각 간선에 흐르는 유량에 해당 간선의 비용을 곱한 값을 모두 합한 것이 총 비용이 된다.
첫째 줄에 정점의 개수 $N$과 간선의 개수 $E$가 공백으로 구분되어 주어진다.
둘째 줄부터 $E$개의 줄에 걸쳐 간선의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 시작 정점 $u$, 도착 정점 $v$, 용량 $capacity$, 단위 비용 $cost$가 공백으로 구분되어 주어진다.
첫째 줄에 정점 1에서 정점 $N$까지의 최대 유량을 출력한다.
둘째 줄에 최대 유량을 흘릴 때의 최소 비용을 출력한다.
4 5
1 2 3 1
1 3 2 2
2 3 1 1
2 4 2 3
3 4 3 1
4
14
2 1
1 2 5 3
5
15