版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明

在 n 个点、m 条有向边的图中，找到使得每个点属于且仅属于一个环的若干个环求环嘚边权和的最小值。

一个环如 1→2→3→1若将每个点拆成两个（如 1 拆为 1 与 1’）就会变成 1→2’→2→3’→3→1’，把标号相同的点间的边去掉就變成了 1→2’，2→3’3→1’。可以看到一个环很清楚地将拆后的点分为两个部分（带 ’ 与不带 ’），这就意味着我们可以用二分图来解決这个问题，且容易发现这是个二分图带权匹配问题用 KM 算法可解。

要注意的坑是本题需要处理重边。