-->
当前位置:首页 > 题库

PROGRAMMING:Minimum cost flow

Luz5年前 (2021-05-10)题库385
This is a template question.
Given a graph, each edge has capacity and cost, and using the unit traffic of each edge needs to pay a specific cost. Given source point $$1 $$and sink point $$n $$, the maximum flow and the minimum cost of the maximum flow of a graph are calculated.
###Input format:
The first line contains two integers, $$n, M $$, indicating that there are $$n $$points, $$M $$edges.
The next $$M $$line starting from the second line, each line has four integers $$s_{ i},t_{ i},c_{ i},w_{ i} $$represents a line from $$s_{ i} $$to $$t_{ i} The side of $$has a capacity of $$C_{ i} $$, the cost of unit flow is $$W_{ i}$$。
The data is guaranteed to be $$1 / Leq n / Leq 400,0 / Leq M / Leq 15000, W_{ i} To ensure that the input data, intermediate results and answers are within the range of 32-bit signed integers.
###Output format:
Two integers in a row represent the maximum flow and the minimum cost that the maximum flow needs to pay.
###Input example:
Here is a set of inputs. For example:
```in
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 example:
The corresponding output is given here. For example:
```out
6 24
```







answer:If there is no answer, please comment