P9902 'PG2' Simulating Maximum Flow

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$.

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 one integer, the maximum flow from $1$ to $n$.

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