{"problem":{"name":"『PG2』弯曲半平面直线同向图最大流","description":{"content":"若能将有向图 $G=(V,E)$ 画在平面上，使得点在一条直线上，任意两条边（可以为弯曲的弧线）仅在重合顶点处相交，且边上的所有点都在直线同侧，且每条边的起点到终点的射线的方向相同，则称 $G$ 是弯曲半平面直线同向图。对于一个弯曲半平面直线同向图给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，求从点 $s$ 到点 $t$ 的最大流。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":550,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9901"},"statements":[{"statement_type":"Markdown","content":"若能将有向图 $G=(V,E)$ 画在平面上，使得点在一条直线上，任意两条边（可以为弯曲的弧线）仅在重合顶点处相交，且边上的所有点都在直线同侧，且每条边的起点到终点的射线的方向相同，则称 $G$ 是弯曲半平面直线同向图。对于一个弯曲半平面直线同向图给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，求从点 $s$ 到点 $t$ 的最大流。\n\n## Input\n\n第一行包含四个正整数 $n$、$m$、$s$、$t$，用空格分隔，分别表示点的个数、有向边的个数、源点序号、汇点序号。\n\n接下来 $m$ 行每行包含三个正整数 $u_i$、$v_i$、$c_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $c_i$。\n\n## Output\n\n一个整数，表示 $s$ 到 $t$ 的最大流。\n\n[samples]\n\n## Note\n\n无重边自环。\n\n对于 $30\\%$ 的数据 $n\\leq 10^3$。\n\n对于 $70\\%$ 的数据 $n\\leq 10^5$。\n\n对于 $100\\%$ 的数据 $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}$，$s\\neq t$。\n\n### 样例解释 1\n![](https://cdn.luogu.com.cn/upload/image_hosting/9qletk0m.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9901","tags":["图论","贪心","网络流","拓扑排序"],"sample_group":[["5 7 1 5\n1 2 1\n2 3 1\n3 4 1\n4 5 1\n2 4 1\n1 4 1\n1 5 1","2"]],"created_at":"2026-03-03 11:09:25"}}