【题意】：给出k个机器，c只牛，每台机器一天最多可以服务m只牛，再给出（k+c）*（k+c)的矩阵，代表每两个实体（牛和牛，牛和机器，机器和机器）之间的直接距离。
问：使全部牛都有机器服务时，牛走的最长路最短是多少？
【题解】：显然这是一个最大值最小化的问题。我们很容易就想到二分枚举答案判断可行性。
首先floyd预处理每对点之间的最短距离，这样我们可以保证牛每次都走最短路到达机器。
之后开始枚举距离（设当前枚举的距离为limit），遍历每个牛与每个机器的最短路，如果maz[i][j] <= limit 我们就连边i->j，表示牛i可以到达机器j，容量为1（inf）。
加入一个源点s，向每个牛连边，容量为1，代表每个牛只能被一个机器服务。
加入一个汇点t，向每个机器连反向边，容量为m，代表每个机器最多可以服务m只牛。
最后跑最大流，如果最大流等于c，表示limit可以满足条件，更新ans就可以了。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 using namespace std;
6 #define maxn 500
7 #define maxm 50005
8 const int INF = 999999999;
9 int k, c, m, n;
10
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14 int maz[maxn][maxn], ans[maxn * maxn];
15 int s, t, tot, tot1, eh[maxn], cur[maxn], pre[maxn], dist[maxn], low[maxn], cnt[maxn];
16
17 void add(int u, int v, int cap, int flow) {
18 Edge e = {u, v, cap, flow, eh[u]};
19 et[tot] = e;
20 eh[u] = tot++;
21 }
22
23 void addedge(int u, int v, int cap) {
24 add(u, v, cap, 0), add(v, u, 0, 0);
25 }
26
27 void init() {
28 tot = 0;
29 memset(eh, -1, sizeof(eh));
30 }
31
32 bool isap(int s, int t, int n) {
33 int u, v, now;
34 memset(dist, 0, sizeof(dist));
35 memset(low, 0, sizeof(low));
36 for(u = 0; u <= n; u++) cur[u] = eh[u];
37 int flow = 0;
38 u = s;
39 low[s] = INF, cnt[0] = n;
40 while(dist[s] < n) {
41 for(now = cur[u]; now != -1; now = et[now].next)
42 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
43 if(now != -1) {
44 cur[u] = pre[v] = now;
45 low[v] = min(low[u], et[now].cap - et[now].flow);
46 u = v;
47 if(u == t) {
48 for(; u != s; u = et[pre[u]].u) {
49 et[pre[u]].flow += low[t];
50 et[pre[u]^1].flow -= low[t];
51 }
52 flow += low[t], low[s] = INF;
53 }
54 } else {
55 if(--cnt[dist[u]] == 0) break;
56 dist[u] = n;
57 cur[u] = eh[u];
58 for(now = eh[u]; now != -1; now = et[now].next)
59 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
60 dist[u] = dist[et[now].v] + 1;
61 cnt[dist[u]]++;
62 if(u != s) u = et[pre[u]].u;
63 }
64 }
65 return flow == c;
66 }
67
68 void floyd() {
69 for(int l = 1; l <= n; l++) {
70 for(int i = 1; i <= n; i++)
71 if(maz[i][l])
72 for(int j = 1; j <= n; j++)
73 if(maz[l][j] && i != j) {
74 if(maz[i][j] == 0) maz[i][j] = maz[i][l] + maz[l][j];
75 else maz[i][j] = min(maz[i][j], maz[i][l] + maz[l][j]);
76 }
77 }
78 tot1 = 0;
79 for(int i = 1; i <= n; i++)
80 for(int j = i + 1; j <= n; j++)
81 ans[tot1++] = maz[i][j];
82 sort(ans, ans + tot1);
83 }
84
85 void build(int limit) {
86 init();
87 for(int i = 1; i <= c; i++)
88 addedge(s, k + i, 1);
89 for(int i = 1; i <= k; i++) {
90 addedge(i, t, m);
91 for(int j = 1; j <= c; j++) {
92 if(maz[i][k + j] <= limit && maz[i][k + j])
93 addedge(k + j, i, 1);
94 }
95 }
96 }
97
98 int solve() {
99 int l = 0, r = tot1 - 1, res = -1;
100 while(l <= r) {
101 int mid = (l + r) >> 1;
102 build(ans[mid]);
103 if(isap(s, t, t - s + 1)) res = ans[mid], r = mid - 1;
104 else l = mid + 1;
105 }
106 return res;
107 }
108
109 int main() {
110 cin >> k >> c >> m;
111 s = 0, t = k + c + 1;
112 n = k + c;
113 for(int i = 1; i <= n; i++)
114 for(int j = 1; j <= n; j++)
115 cin >> maz[i][j];
116 floyd();
117 cout << solve() << endl;
118 return 0;
119 }