SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[POJ2195]Going Home(KM算法)

就是一道KM的模板题,而且建图已经非常显然了。关于KM算法: KM算法流程: (1)初始化可行顶标值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复(2)(3)直到找到相等子图的完备匹配为止上述内容转自:二分图匹配算法总结(phoenixinter),更详细的讲述详见原文。     Read more