此题有多种做法。
使用floyd算法预处理最短路，二分答案，对于每一个mid，如果距离比mid小就连边，
注意把每个机器分成m个点。这样跑一个最大匹配，如果都匹配上就可以减小mid值。
用的算法比较多但是条理很清晰
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f;
int K,C,M;
int Map[maxn][maxn];
int path[maxn][*maxn]; int floyd()
{
int i,j,h,t = K+C;
for(h=;h<=t;h++)
for(i=;i<=t;i++)
for(j=;j<=t;j++)
if(Map[i][j] > Map[i][h]+Map[h][j])
Map[i][j] = Map[i][h]+Map[h][j];
} int BuildGraph(int mid)
{
memset(path,false,sizeof path);
for(int i=;i<=C;i++)
{
for(int j=;j<=K;j++)
{
if(Map[K+i][j] <= mid)
for(int h=;h<=M;h++)
{
path[i][h+(j-)*M] = true;
}
}
}
} int linker[*maxn];
bool used[*maxn]; int Dfs(int u)
{
for(int v=;v<=K*M;v++)
{
if(path[u][v] && !used[v])
{
used[v] = true;
if(linker[v] == - || Dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
} bool MaxMatch()
{
memset(linker,-,sizeof linker);
for(int i=;i<=C;i++)
{
memset(used,false,sizeof used);
if(!Dfs(i)) return false;
}
return true;
} void solve()
{
int low = ,high = *(K+C),mid;
while(high > low)
{
mid = (low+high)/;
BuildGraph(mid);
if(MaxMatch()) high = mid;
else low = mid+;
}
printf("%d\n",low);
} int main()
{
//freopen("input.in","r",stdin);
while(~scanf("%d%d%d",&K,&C,&M))
{
for(int i=;i<=K+C;i++)
{
for(int j=;j<=K+C;j++)
{
scanf("%d",&Map[i][j]);
if(Map[i][j] == ) Map[i][j] = INF;
}
}
floyd();
solve();
}
}