POJ 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
", ans);
148     return 0;
149 }

一直想写SGU187一直也没写过……求各位指点