首页 > 代码库 > POJ 2112 Optimal Milking 最优挤奶方案 Floyd算法+二分查找+最大流
POJ 2112 Optimal Milking 最优挤奶方案 Floyd算法+二分查找+最大流
题目链接：POJ 2112 Optimal Milking
Optimal Milking
Description FJ has moved his K (1 <= K <= 30) milking machines out into the cow pastures among the C (1 <= C <= 200) cows. A set of paths of various lengths runs among the cows and the milking machines. The milking machine locations are named by ID numbers 1..K; the cow locations are named by ID numbers K+1..K+C. Each milking point can "process" at most M (1 <= M <= 15) cows each day. Write a program to find an assignment for each cow to some milking machine so that the distance the furthest-walking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine. Input * Line 1: A single line with three space-separated integers: K, C, and M. * Lines 2.. ...: Each of these K+C lines of K+C space-separated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line. Output A single line with a single integer that is the minimum possible total distance for the furthest walking cow. Sample Input 2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0 Sample Output 2 Source USACO 2003 U S Open | |||||||||
题意：
K个挤奶器（编号1~K），每个每天最多挤M头奶牛。共有C头奶牛（编号K+1~K+C）。挤奶器和奶牛间有不同长度的路。
编写程序，寻找一个方案，安排每头牛到某个挤奶器挤奶，并使得C头奶牛需要走的所有路程的最大路程最小。
分析：
因为有多个挤奶器和多头奶牛，因而要求最短路需要Floyd。然后用最大流算法求解；搜索最大距离的最小值采用二分枚举。
关键问题是构图：
构图思路：
（1）以0为源点s，n+1为汇点t。
（2）s向每头奶牛引一条边，容量为1，代表s走向每头奶牛的最大奶牛数。
（3）每个挤奶器向t引一条边，容量为M，代表每个挤奶器最多向t走M头奶牛。
（4）对于每头奶牛通向每个挤奶器的最短路，如果小于枚举当前距离，说明能够走到，那么从奶牛到挤奶器引一条边，容量为1。
（5）构图完毕。
最大流：
最大流可以用三种方法实现：
（1）EK，普通的SAP算法，因要不断BFS，复杂度较高：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 1010
#define INF 0x3f3f3f3f
int s, t, n, K, C, M;
int a[maxn], pre[maxn];
int flow[maxn][maxn];
int cap[maxn][maxn], mp[maxn][maxn];
int EK()
{
queue<int> q;
memset(flow, 0, sizeof(flow));
int ans = 0;
while(1)
{
memset(a, 0, sizeof(a));
a[s] = INF;
q.push(s);
while(!q.empty()) //bfs找增广路径
{
int u = q.front();
q.pop();
for(int v = 1; v <= n; v++)
if(!a[v] && cap[u][v] > flow[u][v])
{
pre[v] = u;
q.push(v);
a[v] = min(a[u], cap[u][v]-flow[u][v]);
}
}
if(a[t] == 0) break;
for(int u = t; u != s; u = pre[u]) //改进网络流
{
flow[pre[u]][u] += a[t];
flow[u][pre[u]] -= a[t];
}
ans += a[t];
}
return ans;
}
void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++) {
if(mp[i][k] != INF)
for(int j = 1; j <= n; j++)
mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]);
}
}
void build(int mid)
{
n = K+C;
memset(cap, 0, sizeof(cap));
for(int i = K+1; i <= n; i++)
cap[s][i] = 1;
for(int i = 1; i <= K; i++)
cap[i][t] = M;
for(int i = K+1; i <= n; i++)
for(int j = 1; j <= K; j++)
if(mp[i][j] <= mid)
cap[i][j] = 1;
n = K+C+2;
}
void Solve()
{
s = 0, t = n+1;
int l = 0, r = 10000;
while(l < r)
{
int mid = (l+r)/2;
build(mid);
int ans = EK();
if(ans >= C) r = mid;
else l = mid+1;
}
printf("%d\n", r);
}
int main()
{
//freopen("poj_2112.txt", "r", stdin);
while(~scanf("%d%d%d", &K, &C, &M)) {
n = K+C;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == 0) mp[i][j] = INF;
}
Floyd();
Solve();
}
return 0;
}
（2）Dinic，SAP的一种优化方案，保存层次网络，用DFS增广更加快速。#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 250
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap;
};
vector<Edge> EG;
vector<int> G[maxn];
int n, s, t, d[maxn], cur[maxn], mp[maxn][maxn];
int K, C, M;
void addEdge(int from, int to, int cap)
{
EG.push_back((Edge){from, to, cap});
EG.push_back((Edge){to, from, 0});
int x = EG.size();
G[from].push_back(x-2);
G[to].push_back(x-1);
}
bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 0;
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0; i < G[x].size(); i++)
{
Edge& e = EG[G[x][i]];
if(d[e.to] == -1 && e.cap > 0)
{
d[e.to] = d[x]+1;
q.push(e.to);
}
}
}
return (d[t]!=-1);
}
int dfs(int x, int a)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int& i = cur[x]; i < G[x].size(); i++)
{
Edge& e = EG[G[x][i]];
if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0)
{
e.cap -= f;
EG[G[x][i]^1].cap += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Dinic()
{
int ans = 0;
while(bfs())
{
memset(cur, 0, sizeof(cur));
ans += dfs(s, INF);
}
EG.clear();
for(int i = 0; i < n; ++i)
G[i].clear();
return ans;
}
void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++) {
if(mp[i][k] != INF)
for(int j = 1; j <= n; j++)
mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]);
}
}
void build(int mid)
{
n = K+C;
for(int i = K+1; i <= n; i++)
addEdge(s, i, 1);
for(int i = 1; i <= K; i++)
addEdge(i, t, M);
for(int i = K+1; i <= n; i++)
for(int j = 1; j <= K; j++)
if(mp[i][j] <= mid)
addEdge(i, j, 1);
n = K+C+2;
}
void Solve()
{
s = 0, t = n+1;
int l = 0, r = 10000;
while(l < r)
{
int mid = (l+r)/2;
build(mid);
int ans = Dinic();
if(ans >= C) r = mid;
else l = mid+1;
}
printf("%d\n", r);
}
int main()
{
//freopen("poj_2112.txt", "r", stdin);
while(~scanf("%d%d%d", &K, &C, &M)) {
n = K+C;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == 0) mp[i][j] = INF;
}
Floyd();
Solve();
}
return 0;
}（3）ISAP，改进SAP，更加优化，活用层次网络，只需要一遍BFS，然后进行增广。#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 250
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap, flow;
};
vector<Edge> EG;
vector<int> G[maxn];
int n, s, t, d[maxn], cur[maxn], p[maxn], num[maxn], mp[maxn][maxn];
bool vis[maxn];
int K, C, M;
void addEdge(int from, int to, int cap)
{
EG.push_back((Edge){from, to, cap, 0});
EG.push_back((Edge){to, from, 0, 0});
int x = EG.size();
G[from].push_back(x-2);
G[to].push_back(x-1);
}
void bfs()
{
memset(vis, false, sizeof(vis));
queue<int> q;
vis[t] = true;
d[t] = 0;
q.push(t);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = 0; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]^1];
if(!vis[e.from] && e.cap > e.flow) {
vis[e.from] = true;
d[e.from] = d[x]+1;
q.push(e.from);
}
}
}
}
int augment()
{
int x = t, a = INF;
while(x != s) {
Edge& e = EG[p[x]];
a = min(a, e.cap-e.flow);
x = EG[p[x]].from;
}
x = t;
while(x != s) {
EG[p[x]].flow += a;
EG[p[x]^1].flow -= a;
x = EG[p[x]].from;
}
return a;
}
int ISAP()
{
int ans =0;
bfs();
memset(num, 0, sizeof(num));
for(int i = 0; i < n; i++)
num[d[i]]++;
int x = s;
memset(cur, 0, sizeof(cur));
while(d[s] < n) {
if(x == t) {
ans += augment();
x = s;
}
bool flag = false;
for(int i = cur[x]; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]];
if(e.cap > e.flow && d[x] == d[e.to]+1) {
flag = true;
p[e.to] = G[x][i];
cur[x] = i;
x = e.to;
break;
}
}
if(!flag) {
int m = n-1;
for(int i = 0; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]];
if(e.cap > e.flow)
m = min(m, d[e.to]);
}
if(--num[d[x]] == 0) break;
num[d[x] = m+1]++;
cur[x] = 0;
if(x != s)
x = EG[p[x]].from;
}
}
EG.clear();
for(int i = 0; i < n; ++i)
G[i].clear();
return ans;
}
void Floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++) {
if(mp[i][k] != INF)
for(int j = 1; j <= n; j++)
mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]);
}
}
void build(int mid)
{
n = K+C;
for(int i = K+1; i <= n; i++)
addEdge(s, i, 1);
for(int i = 1; i <= K; i++)
addEdge(i, t, M);
for(int i = K+1; i <= n; i++)
for(int j = 1; j <= K; j++)
if(mp[i][j] <= mid)
addEdge(i, j, 1);
n = K+C+2;
}
void Solve()
{
s = 0, t = n+1;
int l = 0, r = 10000;
while(l < r)
{
int mid = (l+r)/2;
build(mid);
int ans = ISAP();
if(ans >= C) r = mid;
else l = mid+1;
}
printf("%d\n", r);
}
int main()
{
//freopen("poj_2112.txt", "r", stdin);
while(~scanf("%d%d%d", &K, &C, &M)) {
n = K+C;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
scanf("%d", &mp[i][j]);
if(mp[i][j] == 0) mp[i][j] = INF;
}
Floyd();
Solve();
}
return 0;
}
时间比较：
前两个分别为EK和ISAP算法，后面的为Dinic。不知为何我写的ISAP时间要比Dinic总是慢那么一点点，不过能顺利过题目就好了。
可以看出EK效率多差了吧：
| Run ID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 13475128 | xxx | 2112 | Accepted | 9584K | 1875MS | G++ | 2266B | 2014-09-25 02:39:13 |
| 13475120 | xxx | 2112 | Accepted | 1328K | 157MS | G++ | 3678B | 2014-09-25 02:35:15 |
| 13475117 | xxx | 2112 | Accepted | 1236K | 125MS | G++ | 2812B | 2014-09-25 02:33:48 |
| 13475113 | xxx | 2112 | Accepted | 1236K | 141MS | G++ | 2814B | 2014-09-25 02:33:09 |
| 13475102 | xxx | 2112 | Accepted | 1236K | 94MS | G++ | 2814B | 2014-09-25 02:26:43 |
POJ 2112 Optimal Milking 最优挤奶方案 Floyd算法+二分查找+最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。