注意这个环指的是简单环
这题用到一个非常 trick 的思路：给你一个图，让你保证每个点恰好处于一个环上。对于任意在环上的点 \(p\) ，出入度都为 \(1\) ，于是我们把它拆成两个点 \(p_{in},p_{out}\) 。则原图上的一条边 \((u,v)\) 在拆点后的图上对应 \((u_{out}, v_{in})\) ，而满足性质当且仅当二分图存在完美匹配。
然后发现边权是显然的 01 分数规划问题，二分答案，然后对于当前图跑一遍 KM 算法 即可，复杂度 \(O(n^3 \log V)\)
标签：二分,环上,牛客,70,挑战赛,out From： https://www.cnblogs.com/fox-konata/p/17763697.html