poj 2112 最大流

题意：K个产奶机，C头奶牛，每个产奶机最多可供M头奶牛使用；并告诉了产奶机、奶牛之间的两两距离Dij(0<=i,j<K+C)。

问题：如何安排使得在任何一头奶牛都有自己产奶机的条件下，奶牛到产奶机的最远距离最短？最短是多少？

二分答案。

注意先floyd求得两两之间最小距离，二分的时候上界不是200。200只是直接相连的最大距离。

  1 // File Name: 2112.cpp
  2 // Author: Missa
  3 // Created Time: 2013/4/11 星期四 14:20:52
  4 
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<cstring>
  8 #include<algorithm>
  9 #include<cmath>
 10 #include<queue>
 11 #include<stack>
 12 #include<string>
 13 #include<vector>
 14 #include<cstdlib>
 15 #include<map>
 16 #include<set>
 17 using namespace std;
 18 #define CL(x,v) memset(x,v,sizeof(x));
 19 #define R(i,st,en) for(int i=st;i<en;++i)
 20 #define LL long long
 21 #define inf 0x3f3f3f3f
 22 int a[240][240];
 23 int K,C,M;
 24 
 25 const int maxn = 240;
 26 int cap[maxn][maxn];
 27 int lev[maxn];
 28 int n, m;
 29 int st, en;
 30 
 31 bool bfs()
 32 {
 33     queue <int> q;
 34     while (!q.empty()) q.pop();
 35     memset(lev, -1, sizeof(lev));
 36     lev[st] = 0;
 37     q.push(st);
 38     while (!q.empty())
 39     {
 40         int u = q.front();q.pop();
 41         for (int v = 0; v <= n+1; ++v)
 42             if (lev[v] == -1 && cap[u][v] != 0)
 43             {
 44                 lev[v] = lev[u] + 1;
 45                 q.push(v);
 46             }
 47     }
 48     return lev[en] != -1;
 49 }
 50 int dfs(int u, int cur_flow)
 51 {
 52     int dt = cur_flow;
 53     if (u == en) return dt;
 54     for (int v = 0; v <= n + 1; ++v)
 55     {
 56         if (cap[u][v] > 0 && lev[u] + 1 == lev[v])
 57         {
 58             int flow = dfs(v, min(dt, cap[u][v]));
 59             cap[u][v] -= flow;
 60             cap[v][u] += flow;
 61             dt -= flow;
 62         }
 63     }
 64     return cur_flow - dt;
 65 }
 66 
 67 int dinic()
 68 {
 69     int cur_flow, ans = 0;
 70     while(bfs())
 71         while(cur_flow = dfs(st, inf))
 72             ans += cur_flow;
 73     return ans;
 74 }
 75 void build(int dis)
 76 {
 77     memset(cap, 0, sizeof(cap));
 78     n = K + C;
 79     st = 0;
 80     en = n + 1;
 81     for (int i = 1; i <= K; ++i)
 82         cap[0][i] += M;
 83     for (int i = K + 1; i <= K + C; ++i)
 84         cap[i][en] += 1;
 85     for (int i = 1; i <= K; ++i)
 86         for (int j = K + 1; j <= K + C; ++j)
 87             if (a[i][j] <= dis)
 88                 cap[i][j] += 1;
 89 }
 90 
 91 
 92 int main()
 93 {
 94     while(~scanf("%d%d%d",&K, &C, &M))
 95     {
 96         for (int i = 1; i <= K + C; ++i)
 97             for (int j = 1; j <= K + C; ++j)
 98             {
 99                 scanf("%d", &a[i][j]);
100                 if (a[i][j] == 0) a[i][j] = inf;
101             }
102         for (int k = 1; k <= K + C; ++k)
103             for (int i = 1; i <= K + C; ++i)
104                 for (int j = 1; j <= K + C; ++j)
105                     a[i][j]= min(a[i][j],a[i][k]+a[k][j]);
106         /*for (int i = 1; i <= K + C; ++i)
107         {
108             for (int j = 1; j <= K + C; ++j)
109                 cout<<a[i][j]<<" ";
110             cout<<endl;
111         }*/
112         int ans = 1, low = 1, high = inf;
113         while(low <= high)
114         {
115             int mid = (low + high) >> 1;
116             build(mid);
117             if (dinic() == C)
118             {
119                 ans = mid;
120                 high = mid - 1;
121             }
122             else
123                 low = mid + 1;
124         }
125         printf("%d\n", ans);
126 
127     }
128     return 0;
129 }