Problem Description

Given $n$ nodes and $m$ directed edges, each edge has a capacity. It is guaranteed that every edge $(u,v,w)$ satisfies $v-u\in[0,k]$. Find the maximum flow from node $1$ to node $n$.

Input Format

The first line contains three positive integers $n$, $m$, and $k$, separated by spaces.

The next $m$ lines each contain three positive integers $u_i$, $v_i$, and $w_i$, separated by spaces, meaning that the $i$-th directed edge starts from $u_i$, ends at $v_i$, and has capacity $w_i$.

Output Format

Output one integer, the maximum flow from $1$ to $n$.

9 21 3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
1 3 1
2 4 1
3 5 1
4 6 1
5 7 1
6 8 1
7 9 1
1 4 1
2 5 1
3 6 1
4 7 1
5 8 1
6 9 1

3

5 10 2
3 5 73
3 4 33
3 5 84
4 5 10
3 4 15
1 2 83
1 3 8
1 3 24
5 5 15
1 2 62

32

Hint

For $20\%$ of the testdata, $n\leq 10^2$, $m\leq 10^4$, $k\leq 2$.

For $40\%$ of the testdata, $n\leq 10^4$, $m\leq 10^6$, $k\leq 2$.

For $60\%$ of the testdata, $n\leq 8\times 10^4$, $m\leq 10^6$, $k\leq 2$.

For $80\%$ of the testdata, $n\leq 8\times 10^4$, $m\leq 10^6$, $k\leq 4$.

For $100\%$ of the testdata, $2\leq n\leq 8\times 10^4$, $1\leq m\leq 10^6$, $2\leq k\leq 7$, $1\leq w\leq 100$.

Translated by ChatGPT 5