关于无向图的最小路径覆盖问题
noip吧
全部回复
仅看楼主
level 11
小白De春天 楼主
我看到的都是这么一个结论：
针对i->j的一条边，建立i->j*,j->i*的两条边，然后求二分图最大匹配。
最小路径覆盖=定点数-最大匹配/2
但是以下这个情景显然就不对啊
这样建立匹配
它的最大匹配数是2，那么结果不就是3-2/2=2了么？
显然答案是1啊
2014年08月27日 04点08分 1
level 11
小白De春天 楼主
没人回答下蒟蒻的问题么。。。。
2014年08月27日 05点08分 2
level 11
_宇过_天晴
最小路径覆盖=定点数-最大匹配
2014年08月27日 05点08分 3
小白De春天
那不是有向图么。。
2014年08月27日 14点08分
_宇过_天晴
回复 小白De春天 :恩，我好像也发现了
2014年08月27日 15点08分
level 13
nodgd
无向图不能这么草率的转二分图，无向图的最小路径覆盖貌似只能带花树
2014年08月27日 06点08分 4
1