1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 using namespace std; 7  8 #define MAX 300 9 #define INF 1000000010 int dis[MAX][MAX];  // 任意两点间的最短路径11 int map[MAX][MAX];  // 容量网络12 bool sign[MAX][MAX];  // 层次网络13 bool used[MAX];  // 标志数组14 int K, C, n, M;15 16 void Build_Graph(int min_max) {17     memset(map, 0, sizeof(map));18     for(int i=K+1; i<=n; i++) map[0][i] = 1;19     for(int i=1; i<=K; i++) map[i][n+1] = M;20     for(int i=K+1; i<=n; i++) {21         for(int j=1; j<=K; j++) {22             if(dis[i][j]<=min_max) map[i][j] = 1;23         }24     }25 }26 bool BFS() {  // BFS构建层次网络27     // 初始化28     memset(used, 0, sizeof(used));29     memset(sign, 0, sizeof(sign));30     int queue[100*MAX] = {0};31     queue[0] = 0;32     used[0] = 1;33     int t = 1, f = 0;34     while(f<t) {35         for(int i=0; i<=n+1; i++) {36             if(!used[i]&&map[queue[f]][i]) {37                 queue[t++] = i;38                 used[i] = 1;39                 sign[queue[f]][i] = 1;40             }41         }42         f++;43     }44     if(used[n+1]) return true;45     else return false;46 }47 int DFS(int v, int sum) {48     int s, t;49     if(v==n+1) return sum;50     s = sum;51     for(int i=0; i<=n+1; i++) {52         if(sign[v][i]) {53             t = DFS(i, min(map[v][i], sum));54             map[v][i] -= t;55             map[i][v] += t;56             sum -= t;57         }58     }59     return s-sum;60 }61 int main() {62     //freopen("test.txt", "r", stdin);63     int L, R, mid, ans;64     while(scanf("%d %d %d", &K, &C, &M)!=EOF) {65         n = K+C;66         // Floyd求任意两点间的最短距离67         for(int i=1; i<=n; i++) {68             for(int j=1; j<=n; j++) {69                 scanf("%d", &dis[i][j]);70                 if(dis[i][j]==0) dis[i][j] = INF;71             }72         }73         for(int k=1; k<=n; k++) {74             for(int i=1; i<=n; i++) {75                 if(dis[i][k]!=INF) {76                     for(int j=1; j<=n; j++) dis[i][j] = min(dis[i][k]+dis[k][j], dis[i][j]);77                 }78             }79         }80         L = 0, R = 10000;81 82         // 二分法搜索83         while(L<R) {84             mid = (L+R)>>1;85             ans = 0;86             // Dinic法求最大流87             Build_Graph(mid);  // 构建容量网络（残余网络）88             while(BFS()) ans += DFS(0, INF);  // 构建层次网络，并进行DFS增广89             if(ans>=C) R = mid;90             else L = mid+1;91         }92         printf("%d\n", R);93     }94     return 0;95 }