poj2112（二分网络流）

/* translation: 有c头奶牛和k台挤奶机，每台挤奶机器最多能够同时服务m头奶牛。且每个物体之间有一定的距离。 求一种分配方案，使得每头奶牛能够分配到机器的同时，最小化奶牛所走的最长距离。 solution: 二分+最大流 看到最小化最大值之类的很容易想到用二分枚举答案。然后就是判定是否可行了。方法是每枚举一次， 就重新建图。建图时将距离超过枚举答案的边删去。然后做网络流，得到最大流后判断是否等于牛的 数量。如果是的话就成功。小于的话说明枚举的答案过小。 note; # 一开始的思路跟上述很类似，不过是在做网络流的时候dfs现判断这条边的距离是否大于枚举的答案， 不是的话，就不走这条边。但是WA了，不知道是没写好还是这个方法有问题。坑待填。如果这个方法 可行的话，就不用每次重复建图了。效率应该会大大提高。 # 这道题用二分图的匈牙利算法（将机器拆点或者用多重匹配）也可行，但是我写了好几次， 不是RE就是WA，好郁闷。 */ #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <queue> using namespace std; const int maxv = 30 + 200 + 20; const int INF = 0x3f3f3f3f; int k, c, m, v, s, t; int dist[maxv][maxv], level[maxv], iter[maxv]; struct Edge { int to, cap, rev; Edge(int to_, int cap_, int rev_):to(to_),cap(cap_),rev(rev_){} }; vector<Edge> G[maxv]; void add_edge(int from, int to, int cap) { G[from].push_back(Edge(to, cap, G[to].size())); G[to].push_back(Edge(from, 0, G[from].size()-1)); } void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> que; level[s] = 0; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for(int i = 0; i < G[v].size(); i++) { Edge& e = G[v][i]; if(e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v, int t, int f) { if(v == t) return f; for(int& i = iter[v]; i < G[v].size(); i++) { Edge& e = G[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; for(;;) { bfs(s); if(level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while((f = dfs(s, t, INF)) > 0) flow += f; } } void build_graph(int mid) { s = v, t = v + 1; for(int i = 0; i < v + 2; i++) G[i].clear(); for(int i = k; i < v; i++) add_edge(s, i, 1); for(int i = 0; i < k; i++) add_edge(i, t, m); for(int i = k; i < v; i++) { for(int j = 0; j < k; j++) if(dist[i][j] <= mid) { add_edge(i, j, 1); } } } bool check(int mid) { build_graph(mid); return max_flow(s, t) == c; } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%d%d%d", &k, &c, &m)) { v = k + c; for(int i = 0; i < v; i++) { for(int j = 0; j < v; j++) { scanf("%d", &dist[i][j]); if(!dist[i][j] && i != j) dist[i][j] = INF; } } for(int t = 0; t < v; t++) { for(int i = 0; i < v; i++) { for(int j = 0; j < v; j++) { dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]); } } } int lb = 0, ub = INF; while(ub - lb > 1) { int mid = (ub + lb) >> 1; if(check(mid)) ub = mid; else lb = mid; } printf("%d\n", ub); } }