题意分析

农夫约翰有 $K$ 台挤奶机和 $C$ 头奶牛，挤奶机编号为 $1$ 到 $K$，奶牛编号为 $K+1$ 到 $K+C$。挤奶机和奶牛之间通过路径相连，路径长度由对称矩阵给出。每台挤奶机每天最多处理 $M$ 头奶牛。目标是找到一种分配方案，使得所有奶牛到其分配的挤奶机的路径中，最长的路径尽可能短（即最小化最大距离），同时确保挤奶机不超负荷。

解题思路

1. Floyd算法预处理：首先使用 Floyd 算法计算所有挤奶机和奶牛之间的最短路径。这一步的目的是为了后续能够快速查询任意两点之间的最短距离。
2. 二分答案：通过二分法枚举可能的最大距离 $D$。对于每个 $D$，检查是否存在一种分配方案，使得所有奶牛到挤奶机的距离不超过 $D$，且每台挤奶机处理的奶牛数不超过 $M$。
3. 网络流建模：对于每个 $D$，构建网络流模型：
   • 源点：连接所有奶牛节点，容量为 $1$（每头奶牛只能分配一台挤奶机）。
   • 中间边：奶牛 $i$ 和挤奶机 $j$ 之间如果最短距离 $e[i][j] \leq D$，则建边，容量为 $1$。
   • 汇点：所有挤奶机节点连接到汇点，容量为 $M$（每台挤奶机最多处理 $M$ 头奶牛）。
4. 最大流验证：计算从源点到汇点的最大流。如果最大流等于 $C$（所有奶牛都被分配），则说明 $D$ 可行，尝试更小的 $D$；否则尝试更大的 $D$。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#define maxn 250
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
	int cnt;
	int k[maxn];
}link[maxn];
bool maps[maxn][maxn];
bool vis[maxn];
int pre[maxn][maxn];
int k,c,m,Max;

void Floyd(){
	for(int p=1;p<=k+c;p++){
		for(int i=1;i<=k+c;i++){
			for(int j=1;j<=k+c;j++){
				if(pre[i][j] > pre[i][p] + pre[p][j]){
					pre[i][j] = pre[i][p] + pre[p][j];
				}
			}
		}
	}
}

bool dfs(int u){
	for(int i=1;i<=k;i++){
		if(vis[i] == false && maps[i][u] == true){
			vis[i] = true;
			if(link[i].cnt < m){
				link[i].k[ ++ link[i].cnt ] = u;
				return true;
			}
			for(int j=1;j<=link[i].cnt;j++){
				if(dfs(link[i].k[j])){
					link[i].k[j] = u;
					return true;
				}
			}
		}
	}
	return false;
}

bool solve(int limit){
	memset(maps, false, sizeof(maps));
	memset(link, 0 ,sizeof(link));
	for(int i=1;i<=k;i++){
		for(int j=k+1;j<=k+c;j++){
			if(pre[i][j] <= limit){
				maps[i][j-k] = true;
			}
		}
	}
	for(int i=1;i<=c;i++){
		memset(vis,false,sizeof(vis));
		if(!dfs(i)) return false;
	}
	return true;
}

int main()
{
	while(scanf("%d%d%d",&k,&c,&m) != -1){
		Max = 0;
		for(int i=1;i<=k+c;i++){
			for(int j=1;j<=k+c;j++){
				scanf("%d",&pre[i][j]);
				if(pre[i][j] == 0) pre[i][j] = inf;
			}
		}
		Floyd();
		for(int i=1;i<=k;i++){
			for(int j=k+1;j<=k+c;j++){
				Max = max(Max, pre[i][j]);
			}
		}
		int l = 0, r = Max, mid;

		while(l < r){
			mid = (l + r) >> 1;
			if(solve(mid)){
				r = mid;

			}
			else l = mid + 1;
		}
		printf("%d\n", r);
	}
	return 0;
}