3673 . [模板題] min cost max flow
Description
這是一道模板題。
給定一個圖，每條邊有容量和費用，使用每條邊的單位流量需要支付特定的費用。給定源點 $1$ 和匯點 $n$，求圖的最大流和最大流需要支付的最小費用。
Input Format
第一行兩個整數 $n$、$m$，表示有 $n$ 個點 $m$ 條邊。
從第二行開始的之後 $m$ 行，每行四個整數 $s_i$、$t_i$、$c_i$、$w_i$ 表示一條從 $s_i$ 到 $t_i$ 的邊，容量為 $c_i$，單位流量需要支付的費用為 $w_i$。
Output Format
一行兩個整數，分別表示最大流和最大流需要支付的最小費用。
Sample Input 1
8 23 2 3 2147483647 1 1 3 1 1 2 4 2147483647 2 1 4 1 2 2 8 2 0 3 5 2147483647 3 1 5 1 3 3 6 2147483647 4 1 6 1 4 3 8 2 0 3 2 2147483647 0 4 6 2147483647 5 1 6 1 5 4 7 2147483647 6 1 7 1 6 4 8 2 0 4 2 2147483647 0 5 8 0 0 5 2 2147483647 0 6 8 0 0 6 2 2147483647 0 7 8 0 0 7 2 2147483647 0
Sample Output 1
6 24
Hints
$1 \le n \le 400, 0 \le m \le 15000, w_i \ge 0$
保证输入数据、中间结果以及答案在 32 位有符号整数范围内
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|
Testdata and Limits
| No. | Time Limit (ms) | Output Limit (KiB) | Subtasks |
|---|