P13942 [EC Final 2019] Flow

$\textit{Pang}$ 的研究兴趣之一是最大流问题。 一个有 $n$ 个顶点的有向图 $G$ 被称为 $\textit{universe}$，如果满足以下条件： - $G$ 是 $k$ 条从顶点 $1$ 到顶点 $n$ 的顶点互不相交、长度相同的简单路径的并集。 一组路径是顶点互不相交的，如果它们没有任何内部顶点相同。 路径中的一个顶点被称为内部顶点，如果它不是该路径的端点。 一条路径是简单的，如果其顶点互不相同。 设 $G$ 是一个有 $n$ 个顶点、$m$ 条边的 $\textit{universe}$ 图。每条边都有一个非负整数容量。你可以进行如下操作任意次（包括 $0$ 次），以使从顶点 $1$ 到顶点 $n$ 的最大流尽可能大： 设 $e$ 是一条容量大于 $0$ 的边。将 $e$ 的容量减少 $1$，并将另一条边的容量增加 $1$。 $\textit{Pang}$ 想知道，最少需要多少次操作才能实现最大流最大化？

第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 100000, 1\leq m \leq 200000$）。 接下来的 $m$ 行，每行包含三个整数 $x, y, z$，表示一条从 $x$ 到 $y$ 的有向边，容量为 $z$（$1 \leq x, y \leq n$, $0\le z\le 1000000000$）。 保证输入是一个 $\textit{universe}$ 图，没有重边和自环。

输出一个整数，表示最少需要的操作次数。

由 ChatGPT 4.1 翻译