|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초 (추가 시간 없음)||256 MB||2||2||2||100.000%|
One of Pang's research interests is the maximum flow problem.
A directed graph $G$ with $n$ vertices is universe if the following condition is satisfied:
A set of paths is vertex-independent if they do not have any internal vertex in common.
A vertex in a path is called internal if it is not an endpoint of that path.
A path is simple if its vertices are distinct.
Let $G$ be a universe graph with $n$ vertices and $m$ edges. Each edge has a non-negative integral capacity. You are allowed to perform the following operation any (including $0$) times to make the maximum flow from vertex $1$ to vertex $n$ as large as possible:\\
Let $e$ be an edge with positive capacity. Reduce the capacity of $e$ by $1$ and increase the capacity of another edge by $1$.\\
Pang wants to know what is the minimum number of operations to achieve it?
The first line contains two integers $n$ and $m$ ($2\leq n\leq 100000, 1\leq m \leq 200000$).
Each of the next $m$ lines contains three integers $x, y$ and $z$, denoting an edge from $x$ to $y$ with capacity $z$ ($1 \leq x, y \leq n$, $0\le z\le 1000000000$).
It's guaranteed that the input is a $universe$ graph without multiple edges and self-loops.
Output a single integer --- the minimum number of operations.
4 3 1 2 1 2 3 2 3 4 3
4 4 1 2 1 1 3 1 2 4 2 3 4 2