题目链接：
题目描述：
有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的最短路径。然后二分枚举奶牛的路径最大距离，每次用多重匹配判断是否合法即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 const int maxn = 250; 9 int maps[maxn][maxn], used[35][15], link[35], vis[35]; 10 int mid, low, high, k, c, m; 11 void floyd (int n) 12 { 13 for (int k=1; k<=n; k++) 14 for (int i=1; i<=n; i++) 15 for (int j=1; j<=n; j++) 16 { 17 maps[i][j] = min (maps[i][j], maps[i][k]+maps[k][j]); 18 high = max (maps[i][j], high); 19 low = min (low, maps[i][j]); 20 } 21 } 22 bool Find (int x) 23 { 24 for (int i=1; i<=k; i++) 25 { 26 if (!vis[i] && maps[x][i]<=mid) 27 { 28 vis[i] = 1; 29 if (link[i]<m) 30 { 31 used[i][link[i] ++] = x; 32 return true; 33 } 34 for (int j=0; j<m; j++) 35 if (Find(used[i][j])) 36 { 37 used[i][j] = x; 38 return true; 39 } 40 } 41 } 42 return false; 43 } 44 bool hungry () 45 { 46 memset (link, 0, sizeof(link)); 47 for (int i=k+1; i<=k+c; i++) 48 { 49 memset (vis, 0, sizeof(vis)); 50 if (!Find(i)) 51 return false; 52 } 53 return true; 54 } 55 int main () 56 { 57 while (scanf ("%d %d %d", &k, &c, &m) != EOF) 58 { 59 int n = k + c; 60 for (int i=1; i<=n; i++) 61 for (int j=1; j<=n; j++) 62 { 63 scanf ("%d", &maps[i][j]); 64 if (maps[i][j] == 0 && i!=j) 65 maps[i][j] = INF; 66 } 67 high = 0, low = INF; 68 floyd (n); 69 int ans; 70 while (low <= high) 71 { 72 mid = (low+high)/2; 73 if (hungry()) 74 { 75 ans = mid; 76 high = mid - 1; 77 } 78 else 79 low = mid + 1; 80 } 81 printf ("%d ", ans); 82 } 83 return 0; 84 }