原题地址：http://poj.org/problem?id=2112
题目大意：有K个挤奶机（标号为1 ~ K）和C头奶牛(编号为K + 1 ~ K + C)，以邻接矩阵的方式给出它们两两之间的距离，每个挤奶机最多能挤M头奶牛的奶，求一种紧挨方案使得所有挤奶机到奶牛的距离的最大值最小
数据范围和一些细节：1 <= K <= 30, 1 <= C <= 200, 1 <= M <= 15, 每条边的长度L 满足 1 <= L <= 200。两点之间如果没有直接连接的边，则在邻接矩阵中给出"0"。邻接矩阵的一行可能会断成多行
题目分析：
这道题和昨天那道2455大同小异，都是使路径长最大值最小。不同的是，2455那道题要求的是路径上的某一条最长边的长度最小，而这道题是满足两点之间的路径长的最大值最小。所以这道题先用Floyd算法预处理出每对顶点之间的最短路，然后二分答案k，将距离小于k的两点之间连容量为1的边，反向边容量为0（注意，在这里连边的时候只能连接挤奶机和奶牛，不能连其它边，我在这里WA了几次）。最后新建源点和汇点，从源点向每台挤奶机连接容量为M的边，从每头奶牛向汇点连接容量为1的边，判断最大流是否等于C。
1 //date 20140119 2 #include <cstdio> 3 #include <cstring> 4 5 const int maxn = 250; 6 const int maxm = 110000; 7 const int INF = 99999999; 8 9 inline int getint() 10 { 11 int ans(0); char w = getchar(); 12 while(‘0‘ > w || w > ‘9‘)w = getchar(); 13 while(‘0‘ <= w && w <= ‘9‘) 14 { 15 ans = ans * 10 + w - ‘0‘; 16 w = getchar(); 17 } 18 return ans; 19 } 20 21 inline int min(int a, int b){return a < b ? a : b;} 22 inline int max(int a, int b){return a > b ? a : b;} 23 24 int K, C, M; 25 int n; 26 int map[maxn][maxn]; 27 28 struct edge 29 { 30 int v, c, next; 31 }E[maxm]; 32 int s, t; 33 int a[maxn], now[maxn]; 34 int lab[maxn]; 35 int nedge; 36 37 inline void add(int u, int v, int c) 38 { 39 E[++nedge].v = v; 40 E[nedge].c = c; 41 E[nedge].next = a[u]; 42 a[u] = nedge; 43 } 44 45 inline void floyd() 46 { 47 for(int k = 1; k <= n; ++k) 48 for(int i = 1; i <= n; ++i) 49 for(int j = 1; j <= n; ++j) 50 { 51 if(i == k || j == k || i == j)continue; 52 map[i][j] = min(map[i][j], map[i][k] + map[j][k]); 53 } 54 } 55 56 inline int label() 57 { 58 static int q[maxn]; 59 int l = 0, r = 1; 60 memset(lab, 0xFF, sizeof lab); 61 q[1] = s; lab[s] = 0; 62 while(l < r) 63 { 64 int x = q[++l]; 65 for(int i = a[x]; i; i = E[i].next) 66 if(E[i].c > 0 && lab[E[i].v] == -1) 67 { 68 lab[E[i].v] = lab[x] + 1; 69 q[++r] = E[i].v; 70 } 71 } 72 return lab[t] != -1; 73 } 74 75 int Dinic(int v, int f) 76 { 77 if(v == t)return f; 78 int res = 0, w; 79 for(int i = now[v]; i; now[v] = i = E[i].next) 80 if((f > 0) && (E[i].c > 0) && (lab[E[i].v] == lab[v] + 1) && (w = Dinic(E[i].v, min(E[i].c, f)))) 81 { 82 E[i].c -= w; 83 E[i ^ 1].c += w; 84 res += w; 85 f -= w; 86 if(f == 0)break; 87 } 88 return res; 89 } 90 91 inline int max_flow() 92 { 93 int ans = 0; 94 while(label()) 95 { 96 for(int i = 1; i <= t; ++i)now[i] = a[i]; 97 ans += Dinic(s, INF); 98 } 99 return ans; 100 } 101 102 inline bool check(int mid) 103 { 104 memset(a, 0, sizeof a); 105 nedge = 1; 106 for(int i = 1; i <= K; ++i) 107 for(int j = K + 1; j <= n; ++j) 108 if(map[i][j] <= mid){add(i, j, 1); add(j, i, 0);} 109 110 for(int i = 1; i <= K; ++i){add(s, i, M); add(i, s, 0);} 111 for(int i = 1; i <= C; ++i){add(i + K, t, 1); add(t, i + K, 0);} 112 return (max_flow() == C) ; 113 } 114 115 inline int solve(int l, int r) 116 { 117 int mid; 118 while(l < r) 119 { 120 mid = (l + r) >> 1; 121 if(check(mid))r = mid; 122 else l = mid + 1; 123 } 124 return l; 125 } 126 127 int main() 128 { 129 K = getint(); C = getint(); M = getint(); 130 n = K + C; s = n + 1; t = n + 2; 131 int minl = INF, maxl = 0; 132 for(int i = 1; i <= n; ++i) 133 for(int j = 1; j <= n; ++j) 134 { 135 map[i][j] = getint(); 136 if(map[i][j] == 0)map[i][j] = INF; 137 } 138 floyd(); 139 for(int i = 1; i <= K; ++i) 140 for(int j = K + 1; j <= n; ++j) 141 { 142 if(map[i][j] == INF)continue; 143 minl = min(minl, map[i][j]); 144 maxl = max(maxl, map[i][j]); 145 } 146 int ans = solve(minl, maxl); 147 printf("%d\n", ans); 148 return 0; 149 }
一直想写SGU187一直也没写过……求各位指点