poj 2112最大流
17200 ワード
标题:K個の産乳機、C頭乳牛、各産乳機は最大M頭乳牛に使用できる.産乳機と乳牛の間の2つの距離Dij(0<=i,j質問:どの乳牛にも自分の産乳機がある条件の下で、乳牛から産乳機までの最も遠い距離が最も短いようにどのように手配しますか?最短はいくらですか.
二分答案
注意まずfloydは2つの間の最小距離を求め、2点の時に上界は200ではありません.200は直接つながっている最大距離にすぎません.
二分答案
注意まず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 }