P2604 [ZJOI2010] Network Expansion

Given a directed graph, each edge has a capacity $c$ and an expansion cost $w$. The expansion cost is the cost required to increase the capacity by $1$. Find: 1. The maximum flow from $1$ to $n$ without any expansion. 2. The minimum total expansion cost required to increase the maximum flow from $1$ to $n$ by $k$.

The first line contains three integers $n, m, k$, denoting the number of vertices, the number of edges, and the required increase in flow. The next $m$ lines each contain four integers $u, v, c, w$, describing a directed edge from $u$ to $v$ with capacity $c$ and expansion cost $w$.

Output one line containing two integers, which are the answers to problems $1$ and $2$ respectively.

- Constraints - For $30\%$ of the testdata, it is guaranteed that $n \le 100$. - For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^3$, $1 \le m \le 5 \times 10^3$, $1 \le k \le 10$, $1 \le u, v \le n$, and $1 \le c, w \le 100$. Translated by ChatGPT 5