放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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//////////////////////////////////
13785858 hankcs 2112 Accepted 588K 188MS C++ 3133B 2015-01-16 21:47:17

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机