poj 2112最大流

17200 ワード

标题:K個の産乳機、C頭乳牛、各産乳機は最大M頭乳牛に使用できる.産乳機と乳牛の間の2つの距離Dij(0<=i,j質問:どの乳牛にも自分の産乳機がある条件の下で、乳牛から産乳機までの最も遠い距離が最も短いようにどのように手配しますか?最短はいくらですか.
二分答案
注意まずfloydは2つの間の最小距離を求め、2点の時に上界は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
", ans); 126 127 } 128 return 0; 129 }