P9901 'PG2' Curved Half-Plane Collinear Same-Direction Graph Maximum Flow

If a directed graph $G=(V,E)$ can be drawn on the plane such that all vertices lie on one straight line, any two edges (which may be curved arcs) intersect only at shared vertices, all points on every edge lie on the same side of the line, and the ray direction from the start point to the end point of each edge is the same, then $G$ is called a curved half-plane collinear same-direction graph. Given $n$ vertices and $m$ directed edges in such a graph, along with the capacity of each edge, find the maximum flow from vertex $s$ to vertex $t$.

The first line contains four positive integers $n$, $m$, $s$, and $t$, separated by spaces, representing the number of vertices, the number of directed edges, the index of the source vertex, and the index of the sink vertex. The next $m$ lines each contain three positive integers $u_i$, $v_i$, and $c_i$, separated by spaces, indicating that the $i$-th directed edge starts from $u_i$, ends at $v_i$, and has capacity $c_i$.

Output one integer, representing the maximum flow from $s$ to $t$.

There are no multiple edges or self-loops. For $30\%$ of the testdata, $n \leq 10^3$. For $70\%$ of the testdata, $n \leq 10^5$. For $100\%$ of the testdata, $2 \leq n \leq 10^6$, $1 \leq m \leq \min\{2\times 10^9,\dfrac{n(n-1)}{2}\}$, $1 \leq c \leq 10^{12}$, and $s \neq t$. ### Sample Explanation 1  Translated by ChatGPT 5