某岛

… : "…アッカリ~ン . .. . " .. .
August 10, 2011

POJ 2112. Optimal Milking

Brief description:

。二分图多重匹配。。)

Analysis:

note: 只有左边的点允许使用多次,从左边和右边出发开始匹配都可以,从右边出发的话,要对左边的点维护一组匹配的 list。。。
。。从左边出发的话只要对每个点 for 循环一次。。(但是同预想中的不太一眼。。后者速度好像要慢一点?。。

匈牙利算法,X 集出发。。(400ms +-。。
匈牙利算法,Y 集出发。。(。。120ms +-。。。

External link:

http://poj.org/problem?id=2112