题目链接：
题目描述：
有k个挤奶机，c头牛，每台挤奶机每天最多可以给m头奶牛挤奶。挤奶机编号从1到k，奶牛编号从k+1到k+c，给出(k+c)*(k+c)的矩阵maps，maps[i][j]代表i到j的距离，问到达挤奶机需要步行最长的奶牛最短要走多少距离？(刚开始看到题目很迷啊，怎么算测试实例答案都是1，原来是非真实存在的路径长度都记为0，那么maps中的零就是INF咯)。
解题思路：
因为要找出步行最长距离的奶牛最少走多远，每个奶牛到达挤奶机之前可以经过多条路径，所以我们要先进行一次floyd进行传递闭包，让maps[i][j]为i到j的最短路径。然后二分枚举奶牛的路径最大距离，每次用多重匹配判断是否合法即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = ;
int maps[maxn][maxn], used[][], link[], vis[];
int mid, low, high, k, c, m;
void floyd (int n)
{
for (int k=; k<=n; k++)
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
{
maps[i][j] = min (maps[i][j], maps[i][k]+maps[k][j]);
high = max (maps[i][j], high);
low = min (low, maps[i][j]);
}
}
bool Find (int x)
{
for (int i=; i<=k; i++)
{
if (!vis[i] && maps[x][i]<=mid)
{
vis[i] = ;
if (link[i]<m)
{
used[i][link[i] ++] = x;
return true;
}
for (int j=; j<m; j++)
if (Find(used[i][j]))
{
used[i][j] = x;
return true;
}
}
}
return false;
}
bool hungry ()
{
memset (link, , sizeof(link));
for (int i=k+; i<=k+c; i++)
{
memset (vis, , sizeof(vis));
if (!Find(i))
return false;
}
return true;
}
int main ()
{
while (scanf ("%d %d %d", &k, &c, &m) != EOF)
{
int n = k + c;
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
{
scanf ("%d", &maps[i][j]);
if (maps[i][j] == && i!=j)
maps[i][j] = INF;
}
high = , low = INF;
floyd (n);
int ans;
while (low <= high)
{
mid = (low+high)/;
if (hungry())
{
ans = mid;
high = mid - ;
}
else
low = mid + ;
}
printf ("%d\n", ans);
}
return ;
}