Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求问此题KM算法的解法……或者没办法用KM算法解? 虽然最小点权覆盖 和 最大边权匹配是对偶问题,但是KM算法中求解的最大权匹配是不断修正顶标的, 也就是说最终虽然求出来了一个最小点权覆盖&&最大权匹配,不过事先却不能知道到底是哪一组顶标下的最小点权覆盖(事实上很可能不是原图中给出的点权) 感觉就像Stoer-Wagner算法求无向图的全局最小割一样,每一次循环都求出了一个s-t最小割,但是在求之前却不知道这一次求出的s-t最小割中的s和t到底是哪两个点。 如果先前给定好两个点x和y,是不能用这个算法来求出x-y最小割的。 不知道我理解的对不对?对的话我就不纠结KM算法了,直接换最大流做…… Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator