P13948 [EC Final 2019] All Pair Maximum Flow

给定一个无向图。你需要计算每一对顶点之间的最大流。 该图具有特殊结构。你可以将其视为一个有 $n$ 个点（顶点）的凸多边形，并有若干线段（边）连接这些顶点。顶点按顺时针顺序从 $1$ 到 $n$ 编号。线段只能在顶点处相交。 每条边都有容量限制。 记从 $s$ 到 $t$ 的最大流为 $f(s,t)$。请输出 $\left(\sum_{s=1}^n \sum_{t=s+1}^n f(s,t) \right) \bmod 998244353$。

第一行包含两个整数 $n$ 和 $m$，表示顶点数和边数（$3\le n\le 200000, n\le m\le 400000$）。 接下来的 $m$ 行，每行包含三个整数 $u, v, w$，表示一条边的两个端点和容量（$1\le u, v\le n, 0\le w\le 1000000000$）。 保证没有重边和自环。 保证对于所有 $i=1,2,\ldots, n$，顶点 $i$ 和顶点 $(i\bmod n)+1$ 之间存在一条边。

输出一行一个整数，表示答案。

由 ChatGPT 4.1 翻译