Description

Alice and Bob studied maximum flow and minimum-cost maximum flow in their graph theory course.

Maximum flow problem: Given a directed graph representing a transportation network, a source $S$ and a sink $T$, each edge has a maximum capacity.

A valid network flow must satisfy:

1. The actual flow on every edge is non-negative and does not exceed its capacity;
2. Except for the source $S$ and the sink $T$, for every other vertex, the total inflow equals the total outflow; the net outflow from $S$ equals the net inflow to $T$, and this value is the total shipped amount (the value of the flow).

The maximum flow problem is to find, for the given network, a flow with the maximum total shipped amount.

The figure above illustrates a maximum flow instance. For each edge, the number on the right is the edge capacity, and the number on the left is the actual flow on that edge in an optimal solution. Note that a maximum flow solution may not be unique.

For a given transportation network, Alice first determines a maximum flow. If there are multiple solutions, Alice may choose any one of them. After that, Bob assigns a unit cost to each edge (each unit cost must be a non-negative real number), subject to the constraint that the sum of unit costs over all edges equals $P$.

The total cost equals the actual flow on each edge multiplied by its unit cost, summed over all edges. Note that Bob knows the maximum flow solution chosen by Alice before assigning unit costs. Alice wants to minimize the total cost, while Bob wants to maximize it. We want to know, if both players use optimal strategies, what are the maximum flow value and the total cost.

Input Format

The first line contains three integers $N, M, P$. $N$ is the number of vertices in the transportation network, $M$ is the number of directed edges, and $P$ is as defined in the statement. To simplify the problem, assume the source $S$ is vertex $1$ and the sink $T$ is vertex $N$.

Each of the next $M$ lines contains three integers $A, B, C$, indicating a directed edge from $A$ to $B$ with capacity $C$.

Output Format

Output two lines. The first line contains an integer, the maximum flow value. The second line contains a real number, the total cost. It is recommended to print at least 4 decimal places.

3 2 1
1 2 10
2 3 15

10
10.0000

Hint

【Sample Explanation】

For Alice, the maximum flow is fixed. The actual flow on both edges is $10$.

For Bob, assign a cost of $0.5$ to the first edge and $0.5$ to the second edge. The total cost is $10 \times 0.5 + 10 \times 0.5 = 10$. It can be proven that no assignment yields a larger total cost.

【Constraints】

For $20\%$ of the testdata, the capacity of every directed edge is $1$.

For $100\%$ of the testdata, $N \le 100$, $M \le 1000$.

For $100\%$ of the testdata: all vertex labels are in the range $1 \sim N$, $1 \le \text{capacity of each edge} \le 50000$, $1 \le P \le 10$, and there are no self-loop edges.

Translated by ChatGPT 5