[USACO2003][poj2112]Optimal Milking(floyd+二分+二分图多重匹配)

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

题意:

有K个挤奶器,C头奶牛,每个挤奶器最多能给M头奶牛挤奶。

每个挤奶器和奶牛之间都有一定距离。

求使C头奶牛头奶牛需要走的路程的最大路程最小。

分析:看到“最大的最小”这种字眼多半是二分枚举,容易想到二分枚举最小的最大路程,设其为max,那么接下来就是判定max合不合法了。故先把那些小于等于max的边加入二分图,如果这个二分图的多重匹配最多能匹配的数量恰恰等于奶牛数,那么说明所有奶牛都能挤到奶,即max合法,反之不合法。

步骤:

1、先floyd处理出每个奶牛和每个挤奶器之间的最短距离。

2、二分枚举最小的最大路程max,并将<=max的边加入二分图,求其多重匹配(本渣这里喜欢直接跑最大流)

3、若多重匹配数==max,则往max左边二分枚举,反之向Max右边二分枚举

原文地址:https://www.cnblogs.com/wmrv587/p/3592865.html