ZOJ Problem Set - 3496
Company A wants to transport as many goods as possible from city S to city T. So they ask company B to do the transportation. There are n cities here in the problem and there are directed roads from cities i to city j with capacity cij.
After a long negotiation, A and B reach a consensus that A first decide how to transport the goods (Of course under the condition that most goods are transported and that the quantity transported in each road cannot exceed the capacity) and then B can assign non-negative integer unit transportation costs to each road such that the total unit transportation costs in all roads sum to P. So the money A has to pay is the sum of costs of all roads while the cost of a certain road is the quantity transported (assigned by A) multiplied by the unit transportation cost (assigned by B). Notice that since the goods are not divisible, the quantity transported for each road should be a non-negative integer.
Of course A wants to minimize the cost and B want to maximize the cost. So you are to work out what the total cost will be?
To make the problem more fun, you should also work out the total cost that A wants to maximize the cost while B wants to minimize it and other conditions keep the same.
There are multiple test cases. The first line of the input is an integer T ≈ 100 indicating the number of test cases.
For each test case, the first line contains 5 integers n, m, S, T, P (2 ≤ n ≤ 500, 0 ≤ m ≤ 10000, 0 ≤ S, T < n, 0 ≤ P ≤ 100000). The next m lines describe the roads between cities. In each of the m lines, 3 integers u, v, c (0 ≤ u, v, 1 ≤ c ≤ 100000) are given indicating a road from u to v with capacity c.
For each test case, output one line with two integers. The first is the total cost that A wants to minimize and B wants to maximize, the second is the total cost that A wants to maximize and B wants to minimize.
1 5 5 0 4 1 0 3 1 0 2 1 3 1 1 2 1 1 1 4 1
A can assign the transported quantity in roads to (1, 0, 1, 0, 1) or (0, 1, 0, 1, 1) in the order as the input. Both of the assignment can transport 1 unit of goods.
So in the first situation, B can assign 1 unit cost to a road that transport 1 unit of goods and 0 to other roads. The total cost is 1. In the second situation, B can assign 1 unit cost to a road that transport 0 units of goods and 0 to other roads. The total cost is 0.
Author: ZHUANG, Junyuan
Contest: The 8th Zhejiang Provincial Collegiate Programming Contest