来源和评测点
USACO 2003 US Open
Poj2112
Caioj1119
题目
【题目大意】
FJ把K个挤奶机搬进了住着C头奶牛的牧场。
挤奶机的编号为1~K,奶牛的编号为K+1~K+C。
每头奶牛到每台挤奶机距离不同,每台挤奶机每天最多服务M头奶牛。
求一种分配方案, 使得走得最远的奶牛走过的距离最小化,输出此距离
重点句:
Cows can traverse several paths on the way to their milking machine. 路径
the distance the furthest-walking cow travels is minimized 走最多的牛的路程最小
【输入格式】
数据第1行是3个整数K,C,M
(1≤K≤30)(1≤C≤200)(1≤M≤15)
接下来是一个(K+C)×(K+C)的距离矩阵。
矩阵元素为正并不超200。距离为0表示两个点之间无边存在。
【输出格式】
输出一个整数,即走得最远的奶牛走过的距离的最小化值。
【输入样例】
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
【输出样例】
2
分析
网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他网络流题目参见:Tag-网络流
其实可以尝试着看看英文题
依旧是folyd,然后二分答案
(反正最终还是要到达挤奶机的)
构图:
从源点到牛建权值为1的边
牛到挤奶机建权值为1的边(当满足二分条件时)
挤奶机到汇点建权值为m的边
相比上一题Ombrophobic Bovines相当无聊,秒AC
代码
|
|
分析2
然鹅通过改进匈牙利算法实现多重二分图匹配
能大幅度加快速度,从而取代网络流
思路来自http://blog.csdn.net/leolin_/article/details/7195205
代码2
|
|