题目描述
Problem Description
Given \( n \) points and \( m \) edges, with each edge having a specified capacity and cost per unit flow, find the maximum flow from point \( 1 \) to point \( n \) and the minimum cost required for this flow.
Note that the graph may contain multiple edges between the same pair of nodes.
Input Format
The first line contains two integers \( n \) and \( m \), representing the number of points and edges, respectively.
The next \( m \) lines each contain four integers \( s_i \), \( t_i \), \( c_i \), and \( w_i \), indicating an edge from \( s_i \) to \( t_i \) with a capacity of \( c_i \) and a cost per unit flow of \( w_i \).
Output Format
Output a single line containing two integers, representing the maximum flow and the minimum cost.
Sample Input and Output
Input Sample #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
Output Sample #1
6 24
Input Sample #2
10 30
1 9 23 2
9 6 29 8
2 8 22 20
7 3 10 16
3 10 18 19
1 2 18 29
9 8 18 15
4 10 5 12
7 5 30 12
7 8 29 7
9 5 20 26
9 4 15 5
9 10 21 6
9 8 15 8
3 4 10 7
3 10 2 5
3 10 26 6
9 3 11 14
6 4 11 7
2 5 1 20
9 5 1 1
6 10 10 17
8 10 29 5
9 4 10 22
5 10 3 14
8 5 16 25
7 10 21 25
1 9 11 16
1 2 14 15
7 9 30 25
Output Sample #2
57 1594
Input Sample #3
10 30
7 4 7 19
9 10 6 12
6 4 13 2
3 5 18 21
8 10 12 4
9 4 11 1
2 5 23 2
2 10 2 7
6 5 13 22
8 5 2 10
5 7 12 14
6 5 22 17
5 10 27 23
1 6 1 21
2 7 30 16
4 5 17 12
1 3 27 25
2 7 19 27
1 9 18 25
4 7 30 28
6 10 20 16
1 2 16 21
3 5 26 2
1 9 1 4
1 2 6 7
2 9 25 28
3 8 11 2
2 3 9 14
9 4 16 2
1 7 3 15
Output Sample #3
47 1821
Notes
For all data, it is guaranteed that \( 1 \le n \le 400 \), \( 0 \le m \le 15000 \), \( 0 \le w_i \le 2^{31} - 1 \), and the answer fits within a 32-bit signed integer.
The problem data is relatively weak and does not include extreme cases for minimum cost maximum flow.
When implementing, if using the Bellman-Ford algorithm, consider the following optimization: if all \( \pi(i) \) remain unchanged during an iteration, stop further iterations.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分