牧场物语:K台挤奶机分布在C头牛间,每台最多同时服务M头牛。给出距离矩阵,求最小化牛的最大路程?
3.5借助水流解决问题的网络流
二分图匹配
一看到最小化最大值(或者最大化最小值),当然是二分搜索了。
先将两点间最短路预处理出来,可以简单warshall_floyd搞定。
接着构建网络流,从s到牛引一条容量1的边,从挤奶机到t引一条容量M的边,
然后对最大路径二分,在二分图匹配建图的时候,牛到挤奶机间距离大于limit的边忽略掉。二分判断条件是,最大流的流量是否等于牛量(南方人你能分明白不),因为题目明确表示至少有一个解使得所有牛都有挤奶机可用。
于是把 POJ 2987 Firing的dinic最大流拖过来就行了。
#include <iostream> #include <vector> #include <queue> using namespace std; ////////////////////////最大流开始////////////////////////////////////// typedef int cap_type; #define MAX_V 200 + 30 + 16 // 用于表示边的结构体(终点、容量、反向边) struct edge { int to, rev; cap_type cap; edge(int to, cap_type cap, int rev) : to(to), cap(cap), rev(rev) {} }; vector <edge> G[MAX_V]; // 图的邻接表表示 int level[MAX_V]; // 顶点到源点的距离标号 int iter[MAX_V]; // 当前弧,在其之前的边已经没有用了 // 向图中加入一条从from到to的容量为cap的边 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)); } // 通过BFS计算从源点出发的距离标号 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); } } } } // 通过DFS寻找增广路 cap_type dfs(int v, int t, cap_type 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]) { cap_type 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; } // 求解从s到t的最大流 cap_type max_flow(int s, int t) { cap_type flow = 0; for (;;) { bfs(s); if (level[t] < 0) { return flow; } memset(iter, 0, sizeof(iter)); cap_type f; while ((f = dfs(s, t, 0x3f3f3f3f3f3f3f3f)) > 0) { flow += f; } } } ///////////////////////////////最大流结束///////////////////////////////////// #define INF 0x3f3f3f3f int K, C, M, V; int graph[MAX_V][MAX_V]; bool check(int limit) { int s = V, t = V + 1; for (int i = 0; i < V + 2; i++) { G[i].clear(); } for (int i = 0; i < K; i++) { add_edge(i, t, M); } for (int i = K; i < V; i++) { add_edge(s, i, 1); } for (int i = 0; i < K; i++) { for (int j = K; j < V; j++) { if (graph[i][j] <= limit) { add_edge(j, i, 1); } } } return max_flow(s, t) == C; } int solve() { // 图预处理,warshall_floyd最小化两点距离 for (int k = 0; k < V; ++k) for (int i = 0; i < V; ++i) for (int j = 0; j < V; ++j) { graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } // 二分搜索 int lb = 0, ub = 200 * V; while (ub - lb > 1) { int mid = (ub + lb) >> 1; (check(mid) ? ub : lb) = mid; } return ub; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif scanf("%d%d%d", &K, &C, &M); V = K + C; for (int i = 0; i < K + C; ++i) { for (int j = 0; j < K + C; ++j) { int d; scanf("%d", &d); graph[i][j] = d ? d : INF; } } printf("%d\n", solve()); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
13785858 | hankcs | 2112 | Accepted | 588K | 188MS | C++ | 3133B | 2015-01-16 21:47:17 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 2112 Optimal Milking 题解 《挑战程序设计竞赛》