POJ 2112 Optimal Milking(最大流+二分)
21762 ワード
タイトルリンク
dinicテンプレートをテストして、このテンプレートが正しいかどうか分かりませんが、その問題はこのdinicでは通れません.最適化を加えるとWAになり,最適化TLEを加えない.
dinicテンプレートをテストして、このテンプレートが正しいかどうか分かりませんが、その問題はこのdinicでは通れません.最適化を加えるとWAになり,最適化TLEを加えない.
1 #include <cstdio>
2 #include <string>
3 #include <cstring>
4 #include <queue>
5 #include <map>
6 #include <algorithm>
7 using namespace std;
8 #define INF 0x3ffffff
9 struct node
10 {
11 int u,v,next,re,w;
12 } edge[200001];
13 int first[501],dis[501];
14 int p[251][251];
15 int t;
16 int sv,ev,K,C,M;
17 void CL()
18 {
19 t = 1;
20 memset(first,-1,sizeof(first));
21 }
22 void add(int u,int v,int w)
23 {
24 edge[t].u = u;
25 edge[t].v = v;
26 edge[t].w = w;
27 edge[t].re = t+1;
28 edge[t].next = first[u];
29 first[u] = t++;
30 edge[t].u = v;
31 edge[t].v = u;
32 edge[t].w = 0;
33 edge[t].re = t-1;
34 edge[t].next = first[v];
35 first[v] = t ++;
36 }
37 int bfs()
38 {
39 int u,v,i;
40 memset(dis,0xff,sizeof(dis));
41 queue<int> que;
42 que.push(sv);
43 dis[sv] = 0;
44 while(!que.empty())
45 {
46 u = que.front();
47 que.pop();
48 for(i = first[u]; i != -1; i = edge[i].next)
49 {
50 v = edge[i].v;
51 if(edge[i].w > 0&&dis[v] < 0)
52 {
53 dis[v] = dis[u] + 1;
54 que.push(v);
55 }
56 }
57 }
58 if(dis[ev] > 0) return 1;
59 else return 0;
60 }
61 int dfs(int u,int step)
62 {
63 int i,a = 0,v,flag = 0;
64 if (u == ev) return step;
65 for (i = first[u];i != -1&&flag < step; i = edge[i].next)//flag<step
66 {
67 v = edge[i].v;
68 if (edge[i].w > 0&& dis[v] == dis[u]+1&&(a = dfs(v,min(step,edge[i].w))))
69 {
70 edge[i].w -= a;
71 flag += a;//
72 edge[edge[i].re].w += a;
73 return a;
74 }
75 }
76 if(flag == 0) dis[u] = -1;//
77 return flag;
78 }
79 void build(int x)
80 {
81 int i,j;
82 CL();
83 for(i = 1; i <= K; i ++)
84 {
85 add(0,i,M);
86 }
87 for(i = 1; i <= K; i ++)
88 {
89 for(j = 1; j <= C; j ++)
90 {
91 if(p[i][j+K] <= x)
92 add(i,K+j,1);
93 }
94 }
95 for(i = 1;i <= C;i ++)
96 {
97 add(i+K,ev,1);
98 }
99 }
100 int fun(int x)
101 {
102 int ans = 0,res;
103 build(x);
104 while(bfs())
105 {
106 while(res=dfs(sv,INF))
107 ans += res;
108 }
109 if(ans == C)
110 return 1;
111 else
112 return 0;
113 }
114 int bin(int l,int r)
115 {
116 int str,mid,end;
117 str = l;
118 end = r;
119 while(str < end)
120 {
121 mid = (str + end)/2;
122 if(fun(mid))
123 {
124 end = mid;
125 }
126 else
127 {
128 str = mid + 1;
129 }
130 }
131 return end;
132 }
133 int main()
134 {
135 int i,j,k;
136 while(scanf("%d%d%d",&K,&C,&M)!=EOF)
137 {
138 for(i = 1;i <= K+C;i ++)
139 {
140 for(j = 1;j <= K+C;j ++)
141 {
142 scanf("%d",&p[i][j]);
143 if(i != j&&p[i][j] == 0)
144 p[i][j] = INF;
145 }
146 }
147 for(i = 1;i <= K+C;i ++)
148 {
149 for(j = 1;j <= K+C;j ++)
150 {
151 for(k = 1;k <= K+C;k ++)
152 {
153 if(p[j][k] > p[j][i] + p[i][k])
154 p[j][k] = p[j][i] + p[i][k];
155 }
156 }
157 }
158 sv = 0;
159 ev = K+C+1;
160 int maxz = 0;
161 for(i = 1;i <= K+C;i ++)
162 {
163 for(j = 1;j <= K+C;j ++)
164 maxz = max(maxz,p[i][j]);
165 }
166 printf("%d
",bin(0,maxz));
167 }
168 return 0;
169 }