K. All Pair Maximum Flow

Codeforces

IDCF10247K

Time6000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex. The graph is special. You can regard it as a convex polygon with $n$ points (vertices) and some line segments (edges) connecting them. The vertices are labeled from $1$ to $n$ in the clockwise order. The line segments can only intersect each other at the vertices. Each edge has a capacity constraint. Denote the maximum flow from $s$ to $t$ by $f (s, t)$. Output $(sum_{s = 1}^n sum_{t = s + 1}^n f (s, t)) bmod 998244353$. The first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3 <= n <= 200000, n <= m <= 400000$). Each of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1 <= u, v <= n, 0 <= w <= 1000000000$). It is guaranteed there are no multiple edges and self-loops. It is guaranteed that there is an edge between vertex $i$ and vertex $(i bmod n) + 1$ for all $i = 1, 2, \\dots, n$. Output the answer in one line. ## Input The first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3 <= n <= 200000, n <= m <= 400000$).Each of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1 <= u, v <= n, 0 <= w <= 1000000000$).It is guaranteed there are no multiple edges and self-loops.It is guaranteed that there is an edge between vertex $i$ and vertex $(i bmod n) + 1$ for all $i = 1, 2, \\dots, n$. ## Output Output the answer in one line. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected graph with: - $ V = \{1, 2, \dots, n\} $, vertices labeled clockwise on a convex polygon. - $ E $: a set of $ m $ edges, each $ (u, v, w) \in E $ with capacity $ w \in \mathbb{Z}_{\ge 0} $. - $ \forall i \in \{1, \dots, n\} $, edge $ (i, (i \bmod n) + 1) \in E $ (polygon boundary edges). Let $ f(s, t) $ denote the maximum flow from vertex $ s $ to vertex $ t $ in $ G $, under edge capacities. **Constraints** 1. $ 3 \le n \le 200000 $ 2. $ n \le m \le 400000 $ 3. $ 0 \le w \le 10^9 $ for all edge capacities 4. No multiple edges or self-loops **Objective** Compute: $$ \left( \sum_{s=1}^{n} \sum_{t=s+1}^{n} f(s, t) \right) \bmod 998244353 $$

API Response (JSON)

{
  "problem": {
    "name": "K. All Pair Maximum Flow",
    "description": {
      "content": "You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex. The graph is special. You can regard it as a convex polygon with $n$ points (vertices) ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10247K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex.\n\nThe graph is special. You can regard it as a convex polygon with $n$ points (vertices) ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with:  \n- $ V = \\{1, 2, \\dots, n\\} $, vertices labeled clockwise on a convex polygon.  \n- $ E $: a set of $ m $ edges, each $ (u, v, w) \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments