POJ 2112 Optimal Milking​ 题解 《挑战程序设计竞赛》

POJ 2112 Optimal Milking

牧场物语：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//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2112 Optimal Milking​ 题解 《挑战程序设计竞赛》