poj 2195 Going Home（最小費用最大流）

http://poj.org/problem?id=2195

題意：一個n*m的矩陣，其中每個'm'代表一個人，每個‘H'代表一個房子，且人和房子的數目相同，要求每個人找到一個屬於自己的房子，每個房子只能住一個人，人到房子的花費就是它們之間的曼哈頓距離。問他們的最小花費。

思路：和 Minimum Cost 一樣，貌似這個更簡單點，因為只需計算一次最小費用最大流。

附加一個超級源點S和超級匯點T。

s 指向所有的人，容量為1，費用為0；
每個人指向所有的房子，容量為INF，費用為人和房子的曼哈頓距離；
所有房子指向t，容量為1，費用為0。
從源點到匯點求費用流。

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;

struct node
{
	int x,y;
}house[maxn],man[maxn];

int n,m;
int hh,mm,num;
int s,t;
int cost[maxn*2][maxn*2],cap[maxn*2][maxn*2];
int mincost;

queue  que;
int inque[maxn*2],pre[maxn*2],dis[maxn*2];

bool spfa()
{
	while(!que.empty()) que.pop();
	memset(inque,0,sizeof(inque));
	memset(pre,-1,sizeof(pre));
	memset(dis,INF,sizeof(dis));

	dis[s] = 0;
	inque[s] = 1;
	que.push(s);

	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inque[u] = 0;

		for(int v = s; v <= t; v++)
		{
			if(cap[u][v] && dis[v] > dis[u]+cost[u][v])
			{
				dis[v] = dis[u]+cost[u][v];
				pre[v] = u;
				if(!inque[v])
				{
					inque[v] = 1;
					que.push(v);
				}
			}
		}
	}
	if(pre[t] == -1)
		return false;
	return true;
}

void MCMF()
{
	while(spfa())
	{
		for(int u = t; u != s; u = pre[u])
		{
			cap[pre[u]][u] -= 1;
			cap[u][pre[u]] += 1;
		}
		mincost += dis[t];
	}
}

int main()
{
	char str[maxn];
	while(~scanf("%d %d",&n,&m))
	{
		if(n == 0 && m == 0) break;
		hh = 0;
		mm = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%s",str+1);
			for(int j = 1; j <= m; j++)
			{
				if(str[j] == 'H')
					house[++hh] = (struct node){i,j};
				if(str[j] == 'm')
					man[++mm] = (struct node){i,j};
			}
		}

		s = 0;
		t = mm+hh+1;

		memset(cost,0,sizeof(cost));
		memset(cap,0,sizeof(cap));

		for(int i = 1; i <= mm; i++)
		{
			for(int j = 1; j <= hh; j++)
			{
				int tmp = abs(man[i].x-house[j].x) + abs(man[i].y-house[j].y);
				cost[i][j+mm] = tmp;
				cost[j+mm][i] = -tmp;
				cap[i][j+mm] = INF;
			}
		}
		for(int i = 1; i <= mm; i++)
		{
			cap[s][i] = 1;
			cap[i+mm][t] = 1;
		}

		mincost = 0;
		MCMF();
		printf("%d\n",mincost);
	}
	return 0;
}