题意:给你K台机器，C头牛，每台机器最多承受M头牛，然后k+C行表示机器到牛的距离，牛到机器的距离，如果距离是0的话表示这两个点道路不存在，要求所有牛到机器中的距离最大值最小
题解:Floyd一下K+C个点之间所有的最短距离,最后距离二分一下，然后就是二分多重匹配在距离的限制下是否可以都匹配成功
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int mx = 305; const int inf = 0x3f3f3f3f; int dis[mx][mx]; int y[mx][mx],len[mx]; int vis[mx]; int g[mx][mx]; int K,C,M; inline bool read(int &x){ x = 0; char c; c = getchar(); if(c==EOF) return false; while(c<'0'||c>'9') c = getchar(); while(c>='0'&&c<='9'){ x = x*10+c-'0'; c = getchar(); } return true; } bool find(int u,int d){ for(int i = 1; i <= K; i++){ int v = g[u][i]; if(v<=d&&!vis[i]){ vis[i] = 1; if(len[i]<M){ y[i][len[i]++] = u; return true; } for(int j = 0; j < len[i]; j++) if(find(y[i][j],d)){ y[i][j] = u; return true; } } } return false; } bool MaxMatch(int d){ memset(len,0,sizeof(len)); for(int i = 1; i <= C; i++){ memset(vis,0,sizeof(vis)); if(!find(i,d)) return false; } return true; } int main(){ while(scanf("%d%d%d",&K,&C,&M)!=EOF){ for(int i = 1; i <= K+C; i++) for(int j = 1; j <= K+C; j++){ scanf("%d",&dis[i][j]); if(i!=j&&!dis[i][j]) dis[i][j] = inf; } for(int k = 1; k <= K+C; k++) for(int i = 1; i <=K+C; i++) for(int j = 1; j <= K+C; j++) dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]); for(int i = K+1; i <= K+C; i++) for(int j = 1; j <= K; j++) g[i-K][j] = dis[i][j]; int l = 1,r = 100000; while(l<r){ int mid = (l+r)/2; if(MaxMatch(mid)) r = mid; else l = mid+1; } printf("%d\n",r); } return 0; }