#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 101
#define MAX_INT 2000000
#define min(a, b) (a) < (b) ? (a) : (b)
#define max(a, b) (a) > (b) ? (a) : (b)
using namespace std;
int weight[N][N]; /* X集合点到Y集合点的权重 */
int lx[N], ly[N]; /* 标号 */
char visitx[N], visity[N]; /* 用于深度搜索,同时可以标记S和T集合的点 */
int mat[N]; /* mat[y] = x,表示集合Y的y点的匹配为x */
int slack[N]; /* slack[x]保存相对与顶点x的最小al,初始时为无穷大, dfs寻找增广路径的时候不断更新,并且会越来越小 */
int nx, ny;
struct position {
int x;
int y;
};
/* 从顶点x开始深度优先寻找增广路径, 寻找的过程中同时更新slack数组
* 和mat数组,若找到返回1
* 若找不到返回0,此时visitx[x] = 1的点属于S集合
* visity[y] = 1的点属于T集合
*/
int find(int x)
{
int y, t;
visitx[x] = 1;
debug("访问顶点X.%d\n", x);
for (y = 1; y <= ny; y++) {
if (!visity[y] && weight[x][y] != 0) {
t = lx[x] + ly[y] - weight[x][y];
if (t != 0) {
slack[x] = min(slack[x], t);
}
else {
visity[y] = 1;
debug("访问顶点Y.%d\n", y);
if ((mat[y] == -1 || find(mat[y]))) {
mat[y] = x;
return 1;
}
debug("否定顶点Y.%d\n", y);
}
}
}
return 0;
}
int main()
{
int x, y, s, min_al, cost, m, n;
char ch;
struct position man[N], home[N];
while (cin>>m>>n, m) {
//初始化l[v]
memset(weight, 0, sizeof(weight));
memset(ly, 0, sizeof(ly));
memset(mat, -1, sizeof(mat));
for (x = 1; x <= N; x++) {
lx[x] = -2000000;
slack[x] = MAX_INT;
}
//输入数据
nx = ny = 0;
for (x = 1; x <= m; x++) {
for (y = 1; y <= n; y++) {
cin >> ch;
if (ch == 'm') {
man[++nx].x = x;
man[nx].y = y;
}
else if (ch == 'H') {
home[++ny].x = x;
home[ny].y = y;
}
}
}
//建图
for (x = 1; x <= nx; x++) {
for (y = 1; y <= ny; y++) {
weight[x][y] = abs(man[x].x-home[y].x) + abs(man[x].y-home[y].y);
weight[x][y] *= -1; /* 题目要求最小权匹配,故把权值乘以-1,转变成求最大权匹配 */
lx[x] = max(lx[x], weight[x][y]); /* lx[x]初始化为最大权值 */
}
}
//给每个顶点寻找增广路径,若找不到就重新标号
for (s = 1; s <= nx;) {
for (;;) {
memset(visitx, 0, sizeof(visitx));
memset(visity, 0, sizeof(visity));
if (find(s)) {
s++;
debug("增广路径找到...\n");
break;
}
debug("从顶点%d找不到增广路径, 更新顶点标号...\n", s);
//在S集合中找最小的lx[x]+ly[y]-weight[x][y], 借助slack数组
min_al = MAX_INT;
for (x = 1; x <= nx; x++) {
if (visitx[x] && slack[x] < min_al) {
min_al = slack[x];
}
}
//更新S集合和T集合顶点标号
for (x = 1; x <= nx; x++) {
if (visitx[x]) lx[x] -= min_al;
}
for (y = 1; y <= ny; y++) {
if (visity[y]) ly[y] += min_al;
}
}
}
//打印匹配结果
for (y = 1; y <= ny; y++) {
if (mat[y] != -1) {
debug("X.%d-->Y.%d %d\n", mat[y], y, weight[mat[y]][y]);
}
}
//计算最大权
cost = 0;
for (x = 1; x <= nx; x++) {
cost += lx[x];
}
for (y = 1; y <= ny; y++) {
cost += ly[y];
}
printf("%d\n", -cost);
}
return 0;
}
分享到:
相关推荐
5. **匹配算法**:如KM算法,用于解决二分图的最大匹配问题(poj1459, poj3436)。 ### 三、数据结构 1. **树和二叉树**:树和二叉树的基本操作和应用(poj1035, poj3080, poj1936)。 2. **堆**:堆排序及其在...
在编程竞赛和算法设计中,最优匹配问题是一个常见的主题,它涉及到寻找两个集合之间的最佳配对,使得某些目标函数(如成本、距离、权重等)达到最优。本文将深入探讨最优匹配问题的解决方案,特别是通过最小费用最大...
包括二分图的最大匹配和KM算法,用于解决资源分配类问题,如poj3041和poj3020。 ### 三、数据结构 #### 字符串处理 如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 ...
- (poj1459, poj3436):例如匈牙利算法(KM算法),用于解决二分图的最大匹配问题。 ### 三、数据结构 1. **链表、栈、队列**: - (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - ...
* 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj2388, poj2299 * 简单并查集的应用 * 哈希表和二分查找等高效查找法 + poj...
- **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大流量。 3. **数据结构**: - **字符串处理**:如poj1035,涉及字符串操作和模式匹配。 - **排序算法**:包括快速排序、归并...
6. **最大流的增广路算法**:如KM算法,求解网络中的最大流量问题,如POJ1459和3436。 ### 数据结构 1. **串**:处理字符串的问题,如POJ1035、3080和1936。 2. **排序**:包括快速排序、归并排序(涉及逆序数)、...
4. **二分图匹配算法**(如KM算法,poj1459, poj3436):用于求解二分图的最大匹配问题,适用于工作分配、婚姻匹配等问题。 #### 数据结构 1. **堆**(如poj1035, poj3080, poj1936):一种特殊的完全二叉树结构,...
(6) 最大流的增广路算法:KM算法 三、数据结构 本部分涵盖了数据结构,包括串、排序、简单并查集的应用、哈希表和二分查找等高效查找法、哈夫曼树和堆、trie树。 (1) 串:poj1035, poj3080, poj1936 (2) 排序:快...
- **定义**: KM算法用于求解最大流问题。 - **应用场景**: 适用于流量网络问题。 - **示例题目**: POJ 1459, POJ 3436 - **注意事项**: 理解流量守恒和容量限制原则。 #### 三、数据结构 **1. 字符串操作** -...
- **【POJ 2195】Going Home**、**【POJ 2400】Supervisor, Supervisee**、**【POJ 2516】Minimum Cost**:这些题目涉及到最小权值匹配,可能需要应用Kuhn-Munkres算法。 - **【POJ 3565】Ants**、**【POJ 3686】The...
6. 增广路算法:KM算法用于求解最大流问题,如poj1459和poj3436。 三、数据结构 1. 串:处理字符串相关问题,如poj1035、poj3080和poj1936。 2. 排序:快速排序、归并排序(涉及逆序数)和堆排序,如poj2388、poj...
二分图匹配问题,可以使用KM算法或最小费用最大流解决,如1325、1469、2195等。 8. **并查集**(Disjoint Set) 并查集用于处理不相交集合的合并与查询,如1861、1182、1308、2524等。 9. **快速查找**(Quick ...
- **最大流**:掌握KM算法,如Poj1459、Poj3436。 3. **数据结构** - **字符串**:学习字符串处理和操作,如Poj1035、Poj3080等。 - **排序**:理解快速排序、归并排序和堆排序,注意与逆序数相关的排序,如Poj...
6. 增广路算法:KM算法,如POJ 1459和POJ 3436。 三、数据结构 1. 串:如POJ 1035和POJ 1936。 2. 排序:快速排序、归并排序和堆排序,涉及逆序数问题,如POJ 2388。 3. 并查集:简单的应用场景。 4. 哈希表和二分...
6. 最大流的增广路算法:KM算法,如POJ1459。 三、数据结构 1. 串:处理字符串的算法,如POJ1035。 2. 排序:快速排序、归并排序(涉及逆序数)和堆排序,如POJ2299。 3. 并查集:简单应用,用于处理集合连接和查询...
7. **二分图**:二分图问题通常与匹配算法相关,例如1325、1469、2195(KM算法或最小费用最大流)和2446、1422、2594。 8. **并查集**:用于处理集合合并和查询问题,推荐1861、1182和1308、2524等题目。 9. **...
6. **最大流的增广路算法**:KM算法用于求解网络中的最大流量,如POJ1459、POJ3436。 **数据结构** 1. **字符串**:如POJ1035、POJ3080和POJ1936中的处理。 2. **排序**:快速排序、归并排序、堆排序,其中归并...
二分图匹配问题是在二分图中找到最大的匹配对数的问题,KM算法是解决该问题的有效方法。 ### 数据结构 1. **树** - POJ 1035, POJ 3080, POJ 1936 树是一种重要的数据结构,常用于构建层次结构的数据模型。 2...
包括深度优先遍历、广度优先遍历、最短路径算法(如Dijkstra、Bellman-Ford、Floyd和堆+Dijkstra)、最小生成树(Prim和Kruskal)、拓扑排序、二分图最大匹配(匈牙利算法)以及最大流的增广路算法(KM算法)。...