E. Flow

Codeforces

IDCF10247E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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 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 <= 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. Output a single integer — the minimum number of operations. ## Input The 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. ## Output Output a single integer — the minimum number of operations. [samples]

**Definitions** Let $ 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) $. Let $ s = 1 $, $ t = n $ be the source and sink vertices. **Constraints** 1. $ 2 \leq n \leq 100000 $, $ 1 \leq m \leq 200000 $ 2. For each edge $ (x, y, z) \in E $: $ 1 \leq x, y \leq n $, $ x \ne y $, $ 0 \leq z \leq 10^9 $ 3. $ 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. 4. 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 $. **Objective** Minimize the number of operations to maximize the maximum $ s $-$ t $ flow.

API Response (JSON)

{
  "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 ...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments