题目大意：
有k个挤奶器，在牧场里有c头奶牛，每个挤奶器可以满足m个奶牛，奶牛和挤奶器都可以看成是实体，现在给出两个实体之间的距离，如果没有路径相连，则为0，现在问你在所有方案里面，这c头奶牛需要走的最大距离的最小值。
分析：
先将题目给出来的距离矩阵跑一下 Floyd 求出全源最短路方便后面建图，
这里注意一下除了对角线的点若有其他点为 0 则应将其值设置为 INF 代表不可达
在使用最大流判断是否存在解的时候，要对每个解都重新建图。
建图需要一个超级源点，把所有的奶牛与源点相连，容量设置为1
把所有的挤奶器与汇点相连，容量为m
然后对于挤奶器和奶牛的距离不超过判断的解的距离的连边，容量设置为1
然后求解即可。如果最大流 == 牛的总数说明可行
AC代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 3000; const int INF = 0x3f3f3f3f; int mp[maxn][maxn]; int L,R; struct Edge { int from,to,cap,flow; Edge(){} Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){} }; struct Dinic { int n,m,s,t; //结点数,边数(包括反向弧),源点与汇点编号 vector<Edge> edges; //边表 edges[e]和edges[e^1]互为反向弧 vector<int> G[maxn]; //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过 int d[maxn]; //d[i]表从起点s到i点的距离(层次) int cur[maxn]; //cur[i]表当前正访问i节点的第cur[i]条弧 void init(int n,int s,int t) { this->n=n,this->s=s,this->t=t; for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back( Edge(from,to,cap,0) ); edges.push_back( Edge(to,from,0,0) ); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int> Q;//用来保存节点编号的 Q.push(s); d[s]=0; vis[s]=true; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0; i<G[x].size(); i++) { Edge& e=edges[G[x][i]]; if(!vis[e.to] && e.cap>e.flow) { vis[e.to]=true; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } //a表示从s到x目前为止所有弧的最小残量 //flow表示从x到t的最小残量 int DFS(int x,int a) { //printf("%d %d ", x, a); if(x==t || a==0)return a; int flow=0,f;//flow用来记录从x到t的最小残量 for(int& i=cur[x]; i<G[x].size(); i++) { Edge& e=edges[G[x][i]]; if(d[x]+1==d[e.to] && (f=DFS( e.to,min(a,e.cap-e.flow) ) )>0 ) { e.flow +=f; edges[G[x][i]^1].flow -=f; flow += f; a -= f; if(a==0) break; } } return flow; } int Maxflow() { int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } return flow; } }DC; void FD(int K,int C) { int n=K+C; L=INF,R=-INF; for(int k=1 ; k<=n ; k++) { for(int i=1 ; i<=n ; i++) { for(int j=1 ; j<=n ; j++) { mp[i][j]=min(mp[i][k]+mp[k][j],mp[i][j]); L=min(L,mp[i][j]); R=max(R,mp[i][j]); } } } } bool ok(int mid,int k,int c,int m) { int n=k+c+1; DC.init(n+1,0,n); for(int i=1 ; i<=c ; i++) DC.AddEdge(0,k+i,1); for(int i=1 ; i<=k ; i++) DC.AddEdge(i,n,m); for(int i=k+1 ; i<=k+c ; i++) for(int j=1 ; j<=k ; j++) if(mp[i][j]<=mid) DC.AddEdge(i,j,INF); return (DC.Maxflow()==c); } int main( ) { int k,c,m; 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",&mp[i][j]); if(i!=j&&mp[i][j]==0) mp[i][j]=INF; } FD(k,c); int ans; while(L<=R) { int mid = (L+R)>>1; if(!ok(mid,k,c,m)) L = mid+1; else { ans=mid; R=mid-1; } } printf("%d ",ans); } return 0; }