{"problem":{"name":"E. Flow","description":{"content":"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 vertex in a path is called internal ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10247E"},"statements":[{"statement_type":"Markdown","content":"One of _Pang_'s research interests is the maximum flow problem. \n\nA directed graph $G$ with $n$ vertices is _universe_ if the following condition is satisfied: \n\nA vertex in a path is called internal if it is not an endpoint of that path.\n\nA path is simple if its vertices are distinct.\n\nLet $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:\n\n Let $e$ be an edge with positive capacity. Reduce the capacity of $e$ by $1$ and increase the capacity of another edge by $1$.\n\n _Pang_ wants to know what is the minimum number of operations to achieve it?\n\nThe first line contains two integers $n$ and $m$ ($2 <= n <= 100000, 1 <= m <= 200000$).\n\nEach of the next $m$ lines contains three integers $x, y$ and $z$, denoting an edge from $x$ to $y$ with capacity $z$ ($1 <= x, y <= n$, $0 <= z <= 1000000000$).\n\nIt's guaranteed that the input is a $u n i v e r s e$ graph without multiple edges and self-loops.\n\n \n\nOutput a single integer — the minimum number of operations.\n\n## Input\n\nThe first line contains two integers $n$ and $m$ ($2 <= n <= 100000, 1 <= m <= 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 <= x, y <= n$, $0 <= z <= 1000000000$).It's guaranteed that the input is a $u n i v e r s e$ graph without multiple edges and self-loops. \n\n## Output\n\nOutput a single integer — the minimum number of operations.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where each edge $ e \\in E $ has non-negative integer capacity $ c(e) $.  \nLet $ s = 1 $, $ t = n $ be the source and sink vertices.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 100000 $, $ 1 \\leq m \\leq 200000 $  \n2. For each edge $ (x, y, z) \\in E $: $ 1 \\leq x, y \\leq n $, $ x \\ne y $, $ 0 \\leq z \\leq 10^9 $  \n3. $ G $ is a *universe* graph: for any simple path from $ s $ to $ t $, all internal vertices have in-degree and out-degree exactly 1 in the subgraph induced by the path.  \n4. Operations: choose an edge $ e $ with $ c(e) > 0 $, reduce $ c(e) $ by 1, increase $ c(e') $ by 1 for some other edge $ e' \\in E $.  \n\n**Objective**  \nMinimize the number of operations to maximize the maximum $ s $-$ t $ flow.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10247E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}