首先floyd求最短路 然后构建网络流，其中源点到每一头牛容量为1，每一个挤奶器到汇点容量为m 牛到挤奶器容量为1.
二分答案，构建网络流。
// ShellDawn // POJ2112 // No.22 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> #define MM(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f using namespace std; #define maxn 300 int n; int D[maxn][maxn]; int E[maxn][maxn]; int V[maxn]; int P[maxn][maxn][2]; int C[maxn]; // 1~c牛，c+1～k+c挤奶器 void init(int gate,int k,int c,int m){ MM(E,0); for(int i=1;i<=c;i++) E[0][i] = 1; for(int i=c+1;i<=c+k;i++) E[i][n+1] = m; for(int i=1;i<=c;i++){ for(int j=c+1;j<=c+k;j++){ if(D[i][j] <= gate){ E[i][j] = 1; } } } } bool BFS(int s){ MM(V,0);MM(C,0); queue<int> q; q.push(s); V[s] = 1; while(!q.empty()){ int now = q.front(); q.pop(); for(int i=1;i<=n+1;i++){ if(V[i] == 0 && E[now][i] > 0){ q.push(i); V[i] = V[now]+1; int c = C[now]; P[now][c][0] = i; P[now][c][1] = E[now][i]; C[now]++; if(i == n+1) return true; } } } return false; } int DFS(int now,int minflow){ if(now == n+1) return minflow; int flow = 0; for(int i=0;i<C[now];i++){ int next = P[now][i][0]; int v = P[now][i][1]; int f = DFS(next,min(minflow,v)); flow += f; minflow -= f; E[now][next] -= f; E[next][now] += f; } return flow; } int main(){ //freopen("A.txt","r",stdin); int k,c,m; cin>>k>>c>>m; n = k + c; MM(D,0x3f); for(int i=c+1;i<=k+c;i++){ for(int j=c+1;j<=k+c;j++){ scanf("%d",&D[i][j]); } for(int j=1;j<=c;j++){ scanf("%d",&D[i][j]); } } for(int i=1;i<=c;i++){ for(int j=c+1;j<=k+c;j++){ scanf("%d",&D[i][j]); } for(int j=1;j<=c;j++){ scanf("%d",&D[i][j]); } } // floyd for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(D[i][j] == 0) D[i][j] = INF; } } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ D[i][j] = min(D[i][j],D[i][k] + D[k][j]); } } } // binary search int L = 0; int R = 10001; int ans = INF; while(L<R){ int mid = (L+R)/2; init(mid,k,c,m); int flow = 0; while(BFS(0)) flow+=DFS(0,INF); if(flow == c){ ans = min(ans,mid); R = mid; }else L = mid + 1; } cout<<ans<<endl; return 0; }