学步园

Problem Address：http://poj.org/problem?id=2195

【前言】

这道题以前看过，但是做错了。

现在学习了网络流，又突然找到了这道题。

【思路】

以m个man和h个house为点，从man到house建立m*h个连接。

每个连接流量为1，花费为两点间的距离，正向弧为正，负向弧为负。

建立源点和汇点。

在源点和man之间建立m个连接，流量为1，花费为0。

在house和汇点之间建立h个连接，流量为1，花费为0。

m个man、h个house以及源点和汇点，构建出一个m+h+2的矩阵。

这样就可以开始最小费用最大流了。

用spfa算法，查询是否存在增广路径。

如果存在，找出最小流量，并更新路径上的结点。

总花费增值为到达汇点的（最小花费*流量）。

继续查询，直到不存在增广路径，即得到最小费用最大流。

用spfa算法的效率是比较高的，用于处理存在负权值边的图。

如果图中存在负权值回路，则不可进行spfa运算。

需先进行拓扑排序，判断是否存在负权值回路。

由于这道题明确不存在，所以不需要判断。

【代码】

#include <iostream>
#include <cmath>
using namespace std;

const int maxn = 200;
const int MAX = 9999999;

int map[maxn+5][maxn+5];
int flow[maxn+5][maxn+5];
int cost[maxn+5][maxn+5];
bool visited[maxn+5];
int d[maxn+5];

int man[maxn][2];
int house[maxn][2];
int num;

int q[maxn*maxn];
int pre[maxn+5];


void init(int m, int h, int size)
{
	int i, j;
	for (i=0; i<size; i++)
	{
		for (j=0; j<size; j++)
		{
			map[i][j] = 0;
			flow[i][j] = 0;
			cost[i][j] = 0;
		}
	}
	for (i=0; i<m; i++)
	{
		for (j=0; j<h; j++)
		{
			map[i][m+j] = 1;
			cost[i][m+j] = abs(man[i][0]-house[j][0]) + abs(man[i][1]-house[j][1]);
			cost[m+j][i] = -cost[i][m+j];
		}
	}
	for (i=0; i<m; i++)
	{
		map[m+h][i] = 1;
	}
	for (i=0; i<h; i++)
	{
		map[m+i][m+h+1] = 1;
	}
}

bool spfa(int s, int t, int size)
{
	int i;
	int u, v;
	for (i=0; i<size; i++)
	{
		visited[i] = false;
		d[i] = MAX;
		pre[i] = -1;
	}
	int head = 1;
	int tail = 0;
	q[0] = s;
	visited[s] = true;
	d[s] = 0;
	while(tail<head)
	{
		u = q[tail];
		tail++;
		visited[u] = false;
		for (v=0; v<size; v++)
		{
			if (map[u][v]>flow[u][v] && d[u]+cost[u][v]<d[v])
			{
				d[v] = d[u] + cost[u][v];
				pre[v] = u;
				if (!visited[v])
				{
					q[head] = v;
					head++;
					visited[v] = true;
				}
			}
		}
	}
	if (pre[t]==-1) return false;
	else return true;
}

int MinCost(int s, int t, int size)
{
	int res = 0;
	int inc, u, v;
	while(spfa(s, t, size))
	{
		inc = MAX;
		for (v=t; v!=s; v=u)
		{
			u = pre[v];
			if (map[u][v]-flow[u][v]<inc)
				inc = map[u][v]-flow[u][v];
		}
		for (v=t; v!=s; v=u)
		{
			u = pre[v];
			flow[u][v] += inc;
			flow[v][u] -= inc;
		}
		res += d[t]*inc;
	}
	return res;
}

int main()
{
	int n, m;
	int i,j;
	char str[maxn];
	while(scanf("%d %d", &n, &m)!=EOF)
	{
		if (n==0 && m==0) break;
		int numman = 0;
		int numhouse = 0;
		for (i=0; i<n; i++)
		{
			scanf("%s", str);
			for (j=0; j<m; j++)
			{
				if (str[j]=='m')
				{
					man[numman][0] = i;
					man[numman][1] = j;
					numman++;
				}
				else if (str[j]=='H')
				{
					house[numhouse][0] = i;
					house[numhouse][1] = j;
					numhouse++;
				}
			}
		}
		num = numman;
		init(num, num, num*2+2);
		printf("%d\n", MinCost(num*2, num*2+1, num*2+2));
	}
	return 0;
}

【P.S】

嗯，这几天做最大流的总是抄袭代码。

嗯，这种习惯不好。

不过学了新的东西。