平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135133585

https://qoj.ac/problem/5048

因此我们可以平面图转对偶图，如下图，假如我们割黄边，就是给所有蓝边加黄边的权值

每次找一条边权最小的边，满足它恰好有一侧是无界区域。将它删
去，将它的边权加到它所在最小环的其他边上。可以证明这个操作前后
任意两点的最大流大小不变。

---

对于转最小环的过程，我们可以按顺式子找。如果跨过了1，就找离目标最近的，也就是大于v的。没有跨过的，就是使编号最小。只要我们每次走的最远，就一定是最小环。