`
kenby
  • 浏览: 723815 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

poj 2195 km算法求最佳匹配

阅读更多

 

#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;
}
分享到:
评论

相关推荐

    ACM-POJ 算法训练指南

    5. **匹配算法**:如KM算法,用于解决二分图的最大匹配问题(poj1459, poj3436)。 ### 三、数据结构 1. **树和二叉树**:树和二叉树的基本操作和应用(poj1035, poj3080, poj1936)。 2. **堆**:堆排序及其在...

    最优匹配题解1

    在编程竞赛和算法设计中,最优匹配问题是一个常见的主题,它涉及到寻找两个集合之间的最佳配对,使得某些目标函数(如成本、距离、权重等)达到最优。本文将深入探讨最优匹配问题的解决方案,特别是通过最小费用最大...

    poj各种分类

    包括二分图的最大匹配和KM算法,用于解决资源分配类问题,如poj3041和poj3020。 ### 三、数据结构 #### 字符串处理 如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 ...

    acm训练计划(poj的题)

    - (poj1459, poj3436):例如匈牙利算法(KM算法),用于解决二分图的最大匹配问题。 ### 三、数据结构 1. **链表、栈、队列**: - (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - ...

    ACM常用算法及其相应的练习题.docx

    * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj2388, poj2299 * 简单并查集的应用 * 哈希表和二分查找等高效查找法 + poj...

    POJ题目简单分类(ACM)

    - **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大流量。 3. **数据结构**: - **字符串处理**:如poj1035,涉及字符串操作和模式匹配。 - **排序算法**:包括快速排序、归并...

    强大的POJ分类——各类编程简单题及其算法分类

    6. **最大流的增广路算法**:如KM算法,求解网络中的最大流量问题,如POJ1459和3436。 ### 数据结构 1. **串**:处理字符串的问题,如POJ1035、3080和1936。 2. **排序**:包括快速排序、归并排序(涉及逆序数)、...

    ACM算法总结--最新总结的ACM算法

    4. **二分图匹配算法**(如KM算法,poj1459, poj3436):用于求解二分图的最大匹配问题,适用于工作分配、婚姻匹配等问题。 #### 数据结构 1. **堆**(如poj1035, poj3080, poj1936):一种特殊的完全二叉树结构,...

    ACM常用算法及其相应的练习题 (2).docx

    (6) 最大流的增广路算法:KM算法 三、数据结构 本部分涵盖了数据结构,包括串、排序、简单并查集的应用、哈希表和二分查找等高效查找法、哈夫曼树和堆、trie树。 (1) 串:poj1035, poj3080, poj1936 (2) 排序:快...

    算法训练方案详解

    - **定义**: KM算法用于求解最大流问题。 - **应用场景**: 适用于流量网络问题。 - **示例题目**: POJ 1459, POJ 3436 - **注意事项**: 理解流量守恒和容量限制原则。 #### 三、数据结构 **1. 字符串操作** -...

    KM匹配题集

    - **【POJ 2195】Going Home**、**【POJ 2400】Supervisor, Supervisee**、**【POJ 2516】Minimum Cost**:这些题目涉及到最小权值匹配,可能需要应用Kuhn-Munkres算法。 - **【POJ 3565】Ants**、**【POJ 3686】The...

    ACM算法总结大全——超有用!

    6. 增广路算法:KM算法用于求解最大流问题,如poj1459和poj3436。 三、数据结构 1. 串:处理字符串相关问题,如poj1035、poj3080和poj1936。 2. 排序:快速排序、归并排序(涉及逆序数)和堆排序,如poj2388、poj...

    NOIP NOI 信息学竞赛 ACM-ICPC POJ(北京大学在线评测系统)刷题推荐 OI复习计划 算法大纲

    二分图匹配问题,可以使用KM算法或最小费用最大流解决,如1325、1469、2195等。 8. **并查集**(Disjoint Set) 并查集用于处理不相交集合的合并与查询,如1861、1182、1308、2524等。 9. **快速查找**(Quick ...

    很快速的提高算法能力.docx

    - **最大流**:掌握KM算法,如Poj1459、Poj3436。 3. **数据结构** - **字符串**:学习字符串处理和操作,如Poj1035、Poj3080等。 - **排序**:理解快速排序、归并排序和堆排序,注意与逆序数相关的排序,如Poj...

    【最新+免费】ACM主要算法.doc

    6. 增广路算法:KM算法,如POJ 1459和POJ 3436。 三、数据结构 1. 串:如POJ 1035和POJ 1936。 2. 排序:快速排序、归并排序和堆排序,涉及逆序数问题,如POJ 2388。 3. 并查集:简单的应用场景。 4. 哈希表和二分...

    ACMer需要掌握的算法讲解.pdf

    6. 最大流的增广路算法:KM算法,如POJ1459。 三、数据结构 1. 串:处理字符串的算法,如POJ1035。 2. 排序:快速排序、归并排序(涉及逆序数)和堆排序,如POJ2299。 3. 并查集:简单应用,用于处理集合连接和查询...

    算法学习攻略

    7. **二分图**:二分图问题通常与匹配算法相关,例如1325、1469、2195(KM算法或最小费用最大流)和2446、1422、2594。 8. **并查集**:用于处理集合合并和查询问题,推荐1861、1182和1308、2524等题目。 9. **...

    ACM算法总结大全——超有用!.pdf

    6. **最大流的增广路算法**:KM算法用于求解网络中的最大流量,如POJ1459、POJ3436。 **数据结构** 1. **字符串**:如POJ1035、POJ3080和POJ1936中的处理。 2. **排序**:快速排序、归并排序、堆排序,其中归并...

    北大、杭电ACM试题分类

    二分图匹配问题是在二分图中找到最大的匹配对数的问题,KM算法是解决该问题的有效方法。 ### 数据结构 1. **树** - POJ 1035, POJ 3080, POJ 1936 树是一种重要的数据结构,常用于构建层次结构的数据模型。 2...

    北大acm试题

    包括深度优先遍历、广度优先遍历、最短路径算法(如Dijkstra、Bellman-Ford、Floyd和堆+Dijkstra)、最小生成树(Prim和Kruskal)、拓扑排序、二分图最大匹配(匈牙利算法)以及最大流的增广路算法(KM算法)。...

Global site tag (gtag.js) - Google Analytics