某島

… : "…アッカリ~ン . .. . " .. .
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