시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 (추가 시간 없음) | 256 MB | 5 | 4 | 4 | 100.000% |
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 $\left(\sum_{s=1}^n \sum_{t=s+1}^n f(s,t) \right) \bmod 998244353$.
The first line contains two integers $n$ and $m$, representing the number of vertices and edges ($3\le n\le 200000, n\le m\le 400000$).
Each of the next $m$ lines contains three integers $u, v, w$ denoting the two endpoints of an edge and its capacity ($1\le u, v\le n, 0\le w\le 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,\ldots, n$.
Output the answer in one line.
6 8 1 2 1 2 3 10 3 4 100 4 5 1000 5 6 10000 6 1 100000 1 4 1000000 1 5 10000000
12343461