NC51316 Going Home （最大完美匹配）

题目描述：
在网格地图上有 n 个小人和 n 个房子，在单位时间内，每个小人都可以水平或垂直移动一个格子。

每个小人移动一步都会花费你 1 美金，直到他进入到一间房子里为止，每间房子只能容纳一人。

你需要计算，所有小人都进入到房子里，你所需要花费的金额最少是多少。

在输入的地图场景中，. 表示空地，H 表示房子，m 表示小人。

地图足够大，并且小人在不进入房间的情况下，也可以踩在有房间的格子上。

输入格式
输入包含多组测试数据。

每组测试数据第一行包含两个整数 N 和 M，表示地图大小为 N 行 M 列。

接下来 N 行每行包含 M 个字符，表示完整的地图场景。

房屋数量与人数量相同，且不超过 100 个。

当输入一行为 0 0 时，表示输入终止。

输出格式
每组数据输出一个整数，表示最少花费。

每个结果占一行。

数据范围
2≤N,M≤100
输入样例：

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出样例：

2
10
28
1
2
3

思路：
将所有的距离改成复数，这样就是一道负权值得最大完美匹配问题。只需要在统计res的时候讲res取相反数就可以了。
板子题
代码：

#include
#include
#include
#define  x first
#define y second
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e3;
typedef pair<int,int>PII;
int g[N][N];
bool vx[N],vy[N];
int lx[N],ly[N];
int match[N];
bool dfs(int u,int m)
{
	vx[u]=true;
	for(int i=0;i<m;i++)
	{
		if(!vy[i] && lx[u] + ly[i] == g[u][i])
		{
			vy[i]=true;
			if(match[i] == -1 || dfs(match[i],m))
			{
				match[i] = u;
				return true;
			}
		}
	}
	return false;
}
void KM(int n,int m)
{
	memset(lx,-INF,sizeof lx);
	memset(ly,0,sizeof ly);
	memset(match,-1,sizeof match);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			lx[i]=max(lx[i],g[i][j]);
		}
	}
	for(int i=0;i<n;i++)
	{
		while(1)
		{
			memset(vx,0,sizeof vx);
			memset(vy,0,sizeof vy);
			if(dfs(i,m))
			{
				break;
			}
			int d=INF;
			for(int j=0;j<n;j++)
			{
				if(vx[j])
				{
					for(int k=0;k<m;k++)
					{
						if(!vy[k])
						{
							d=min(d,lx[j]+ly[k]-g[j][k]);
						}
					}
				}
			}
			if(d==INF)
			{
				return;
			}
			for(int j=0;j<n;j++)
			{
				if(vx[j])
				{
					lx[j]-=d;
				}
			}
			for(int j=0;j<n;j++)
			{
				if(vy[j])
				{
					ly[j]+=d;
				}
			}
		}
	}
}
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		vector<PII>ve1,ve2;
		if(n==0 || m==0)
		{
			break;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				char t;
				cin>>t;
				if(t=='H')
				{
					ve2.push_back({i,j});
				}
				else if(t=='m')
				{
					ve1.push_back({i,j});
				}
			}
		}
		for(int i=0;i<ve1.size();i++)
		{
			for(int j=0;j<ve2.size();j++)
			{
				g[i][j]=-(abs(ve1[i].x-ve2[j].x)+abs(ve1[i].y-ve2[j].y));
			}
		}
		KM(ve1.size(),ve2.size());
		int res=0;
		for(int i=0;i<ve1.size();i++)
		{
			res-=g[match[i]][i];
		}
		cout<<res<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129