Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 二分答案+网络流判断可行性，附AC代码

Posted by yousiki at 2016-07-30 20:31:08 on Problem 2112
```前辈有句话总结的好——最大值最小，最小值最大，十有八九是二分。Orz

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

/* POJ 2112 */

const int INF = 0x3f3f3f3f;
const int maxK = 35, maxC = 205, maxM = 20, maxV = 300;

int K, C, M, V;
int G[maxV][maxV];
int cap[maxV][maxV], dep[maxV], St, Ed;

inline void buildGraph(int limit) {

/* prepare */
memset(cap, 0, sizeof(cap));
St = 0, Ed = V + 1;

/* milkingMachines */
for (int i = 1; i <= K; i++)
cap[St][i] += M;

/* cows */
for (int i = K + 1; i <= V; i++)
cap[i][Ed] += 1;

/* cows and milingMachines */
for (int i = 1; i <= K; i++)
for (int j = K + 1; j <= V; j++)
cap[i][j] += (G[i][j] <= limit);

}

inline bool dinicBFS(void) {

/* prepare for BFS */
memset(dep, -1, sizeof(dep));
int que[maxV], head = 0, tail = 0;

/* start of BFS */
que[tail++] = St, dep[St] = 0;
for (int v = 0; v <= Ed; v++)
if (dep[v] == -1 && cap[u][v])
dep[v] = dep[u] + 1, que[tail++] = v;
}

return dep[Ed] != -1;

}

inline int dinicDFS(int u, int f) {

if (u == Ed)return f;

int tmp = f, newFlow;
for(int v=0;v<=Ed;v++)
if (dep[v] == dep[u] + 1 && cap[u][v] > 0) {
newFlow = dinicDFS(v, min(tmp, cap[u][v]));
cap[u][v] -= newFlow;
cap[v][u] += newFlow;
tmp -= newFlow;
}

return f - tmp;

}

inline int dinic(void) {

/* maxFlow */
int maxFlow = 0;
while (dinicBFS())
maxFlow += dinicDFS(St, INF);

return maxFlow;

}

inline bool check(int mid) {

buildGraph(mid);
int maxFlow = dinic();

return maxFlow == C;

}

inline void Floyd(void) {

/* FloydAlgorithm */
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

}

signed main(void) {

#ifndef ONLINE_JUDGE
printf(" POJ 2112 \n By YOUSIKI \n");
#endif

/* input */
scanf("%d%d%d", &K, &C, &M), V = K + C;
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
scanf("%d", &G[i][j]);
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
if (G[i][j] == 0)G[i][j] = INF;

Floyd();

/* binarySearch */
int left = 1, right = V * 200, mid, ans = 1;
while (left <= right) {
mid = (left + right) >> 1;
if (check(mid))right = mid - 1, ans = mid;
else left = mid + 1;
}

/* output */
printf("%d\n", ans);

#ifndef ONLINE_JUDGE
system("pause");
#endif

}	// By YOUSIKI```

Followed by: