`

【完美匹配-KM算法】HDU总结

阅读更多
KIDx 的解题报告
题目链接:http://acm.hdu.edu.cn/diy/contest_show.php?cid=12698




首先献上模板:
#define M 505
#define inf 0x3fffffff
bool sx[M], sy[M];
int match[M], w[M][M], n, m, d, lx[M], ly[M];
//n:左集元素个数; m:右集元素个数
void init ()
{
    memset (w, 0, sizeof(w));    //不一定要,求最小值一般要初始化为负无穷!
}

bool dfs (int u)
{
	int v; sx[u] = true;
	for (v = 0; v < m; v++)
	{
		if (!sy[v] && lx[u]+ly[v]==w[u][v])
		{
			sy[v] = true;
			if (match[v] == -1 || dfs (match[v]))
			{
				match[v] = u;
				return true;
			}
		}
	}
	return false;
}

int KM ()
{
	int i, j, k, sum = 0;
	memset (ly, 0, sizeof(ly));
	for (i = 0; i < n; i++)
	{
		lx[i] = -inf;
		for (j = 0; j < m; j++)
			if (lx[i] < w[i][j])
				lx[i] = w[i][j];
	}
	memset (match, -1, sizeof(match));
	for (i = 0; i < n; i++)
	{
		while (1)
		{
			memset (sx, false, sizeof(sx));
			memset (sy, false, sizeof(sy));
			if (dfs (i))
				break;
			d = inf;
			for (j = 0; j < n; j++)
				if (sx[j])
					for (k = 0; k < m; k++)
						if (!sy[k])
							d = min (d, lx[j]+ly[k]-w[j][k]);
			if (d == inf)    //找不到完美匹配
				return -1;
			for (j = 0; j < n; j++)
				if (sx[j])
					lx[j] -= d;
			for (j = 0; j < m; j++)
				if (sy[j])
					ly[j] += d;
		}
	}
	for (i = 0; i < m; i++)
		if (match[i] > -1)
			sum += w[match[i]][i];
	return sum;
}

第一题:http://acm.hdu.edu.cn/showproblem.php?pid=2255
直接输入w[i][j]边权值建图套模板就可以了

第二题:http://acm.hdu.edu.cn/showproblem.php?pid=1533
将m的坐标记录到左集,h的坐标记录到右集,w[i][j]表示第i个m到第j个h的距离
w[i][j]=△x+△y 然后因为是求最小值,而KM是求最大值
所以只要这样:w[i][j] = -w[i][j]建图再套模板输出【-sum】就ok!

第三题:http://acm.hdu.edu.cn/showproblem.php?pid=1853
直接建图,注意有重边哦!
if (-c > w[a][b])
    w[a][b] = -c;

当木有完美匹配输出-1

第四题:http://acm.hdu.edu.cn/showproblem.php?pid=3488
跟第三题几乎一样

第五题:http://acm.hdu.edu.cn/showproblem.php?pid=3435
跟第三题代码基本上一样,只是要双向建图,也有重边

第六题:http://acm.hdu.edu.cn/showproblem.php?pid=2426
左集是学生,右集是房子,注意 w[i][j] < 0 不可匹配,最后无法完美匹配输出-1

第七题:http://acm.hdu.edu.cn/showproblem.php?pid=2853
题目要求匹配最大值和至少要改变多少个原有匹配
思路:让原有匹配更有优势就可以了
实现:所有权值扩大100倍,原有匹配【例如a匹配b】w[a][b]++
设结果是res
最大值:res/100
至少改变个数:n - res%100


第八题:http://acm.hdu.edu.cn/showproblem.php?pid=3718
题目求的是两字符串的最大相似度
思路:因为第一个串的一种字母只能匹配第二个串的一种字母,所以可以转化为求
【字母的最大匹配值/n】
建图:【例】



第九题:http://acm.hdu.edu.cn/showproblem.php?pid=3722
直接按题目要求建图,注意跟自己匹配的值是0,w[i][i]=0

第十题:http://acm.hdu.edu.cn/showproblem.php?pid=3395
直接按题目要求建图就可以了

第十一题:http://acm.hdu.edu.cn/showproblem.php?pid=2282
建图:多余的1分别跟所有的0算出最小距离,例如3,多了2个1,要把他们跟所有0匹配,左集是1,右集是这n个数【限制匹配条件(=0)就可以了】
左集个数为m,表示有多少个1需要移动
m = 0;
for (i = 0; i < n; i++)
{
    if (a[i] > 1)
    {
        for (j = 1; j < a[i]; j++)
        {
            for (k = 0; k < n; k++)
                if (a[k] == 0)
                    w[m][k] = -min (abs(k-i), n-abs(k-i));
            m++;
        }
    }
}


第十二题:http://acm.hdu.edu.cn/showproblem.php?pid=2813
这题比较容易超时……
用STL的map把字符串映射为序号
m1.clear();
m2.clear();
k1 = k2 = 1;
while (q--)
{
    scanf ("%s%s%d", s, p, &x);
    string a(s);
    string b(p);
    if (m1[a] == 0)
        m1[a] = k1++;
    if (m2[b] == 0)
        m2[b] = k2++;
    w[m1[a]][m2[b]] = -x;
}


第十三题:http://acm.hdu.edu.cn/showproblem.php?pid=2448
这题要读懂题目意思!
题意:n艘船要分别回到n个码头,另外有m个采矿点,一开始n艘船所在采矿点已经给出,采矿点与采矿点之间给出k条路【双向的】,码头与采矿点之间给出p条路,由于船进入码头后就不会出来,所以这条路是单向的!
实现:最短路+KM

第十四题:http://acm.hdu.edu.cn/showproblem.php?pid=2236
题意:n×n的矩阵中,没行找一个元素,每个元素之间不可同列,求这n个元素的最大值-最小值的最小差
思路:暴力枚举差值【由于元素的值0<= x <=100, 差值的范围也只能是[0,100]】
匈牙利检验就可以了
bool KM (int low, int high)
{
    int i;
    memset (match, -1, sizeof(match));
    for (i = 0; i < n; i++)
    {
        memset (vis, false, sizeof(vis));
        if (!dfs (i, low, high))
            return false;
    }
    return true;
}


第十五题:http://acm.hdu.edu.cn/showproblem.php?pid=3315
默认匹配是w[i][i]
si打赢xj,w[i][j] = v[i]
如果si输了,w[i][j] = -v[i]
所有权值扩大100倍,w[i][i]++优先匹配
相似度=(res%100*100/n)%
  • 大小: 27.1 KB
  • 大小: 1.1 KB
  • 大小: 1.6 KB
3
13
分享到:
评论
4 楼 基德KID.1412 2012-05-30  
lijunle 写道
KIDx大神,我想问下,第14题。我用二分+枚举差值,跑最快也要900+ms。你的枚举差值就行的思路是什么意思?为什么你的代码跑得这么快?

先将矩阵中的元素不重复地存放到num数组中,然后枚举
for (i = 0; i <= 100; i++)
    for (j = 0; j < k; j++)
        if (KM (num[j], num[j]+i))
            goto end;
3 楼 lijunle 2012-05-30  
KIDx大神,我想问下,第14题。我用二分+枚举差值,跑最快也要900+ms。你的枚举差值就行的思路是什么意思?为什么你的代码跑得这么快?
2 楼 基德KID.1412 2012-02-10  
暴风雪 写道
话说,这篇总结不错啊,肿么那么多踩的,同情博主

踩踩更健康
1 楼 暴风雪 2012-02-06  
话说,这篇总结不错啊,肿么那么多踩的,同情博主

相关推荐

    2-sat---hdu3062

    2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。

    二分图的完美匹配 KM算法.docx

    在给定的题目链接中,例如http://acm.hdu.edu.cn/showproblem.php?pid=1533,这些题目都是关于二分图完美匹配的应用实例,通过KM算法可以高效地找到解决方案。理解并掌握KM算法对于解决这类问题至关重要。

    算法-连连看(HDU-1175)(包含源程序).rar

    本压缩包中的资源——"算法-连连看(HDU-1175)(包含源程序).pdf"很可能提供了一个关于如何用编程语言实现连连看算法的详细讲解,包括源代码示例。 连连看算法的实现主要分为以下几个步骤: 1. **游戏初始化**:...

    算法-命运(HDU-2571)(包含源程序).rar

    标题中的“算法-命运(HDU-2571)”是一个编程竞赛题目,通常来自于各大在线编程平台,如HDU(杭州电子科技大学在线评测系统)等。这类问题旨在测试和提升参赛者的算法设计和编程能力。从描述来看,这个压缩包包含了...

    HDU.rar_hdoj 2000 2999 chm_hdoj 2000-2099_hdu_hdu acm 20_杭电ACM

    这份名为"HDU.rar"的压缩包文件,包含了针对杭电(Hangzhou Dianzi University,简称HDU)ACM竞赛平台上的2000至2099号题目的一系列解题报告。这些报告以".chm"(Compiled Help Manual)格式存储,是专门为ACM(国际...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    算法-数塔(HDU-2084).rar

    标题中的“算法-数塔(HDU-2084)”是指一个编程竞赛题目,源自杭州电子科技大学(HDU)的在线编程平台。在这个问题中,参赛者被要求解决一个名为“数塔”的算法挑战。数塔问题通常涉及到递归、深度优先搜索(DFS)...

    zyq2652192993zyq#Advance-Algorithm#HDU-1711 Number Sequence(KMP算

    HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh

    ACM-HDU涉及了很多算法

    解决方法包括Kuhn-Munkres算法(KM算法)或匈牙利算法,它们通过增广路径来找到最大匹配。 2. **博弈**:博弈论是研究决策者之间冲突与合作的数学理论。在ACM中,博弈问题通常涉及到棋盘游戏或策略选择,如Nim游戏...

    HDU算法讲解的PPT

    HDU算法讲解的PPT是一份非常有价值的教育资源,由知名教育机构HDU(杭州电子科技大学)的lcy老师精心制作并讲解。这份PPT涵盖了算法的各个方面,是学习和提升算法能力的理想材料。标签“算法”、“讲解”和“经典”...

    2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)rar

    在编程竞赛的世界里,HDU(Hangzhou Dianzi University)举办的Multi-University Training Contest一直备受关注,尤其是2019年的第六场赛事,更是吸引了众多参赛者一展才华。这个名为"2019 Multi-University ...

    hdu ACM代码 每种算法都有分类

    HDU ACM代码集合是针对ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)的一份资源,这个压缩包中的代码涵盖了多种算法,是参赛者或对算法学习感兴趣的人宝贵的参考资料。ACM竞赛旨在...

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    ACM HDU 2000-2099 解题报告 杭电 ACM

    通过阅读这份《ACM HDU 2000-2099 解题报告》,读者不仅可以学习到具体的算法知识,还能掌握如何在实际编程竞赛中应用这些知识,从而提高自己的编程竞技水平。同时,对于准备参加ACM/ICPC或其他算法竞赛的学生来说,...

    算法-畅通工程(HDU-1232)(包含源程序).rar

    在提供的压缩文件中,"算法-畅通工程(HDU-1232)(包含源程序).pdf"很可能包含了问题的详细描述、数据格式、输入输出示例以及可能的解题思路或参考代码。对于学习和提升算法能力来说,分析并理解这些源程序是非常...

    算法-欧拉回路(HDU-1878)(包含源程序).rar

    HDU-1878 是一个算法竞赛题目,这类题目通常要求参赛者编写程序来解决特定的数学或逻辑问题。在这个问题中,参赛者可能需要设计一个算法,输入一张图(可能是通过邻接矩阵或邻接表来表示),然后判断这个图是否包含...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    算法-超级楼梯(HDU-2040)(包含源程序).rar

    压缩包内的“算法-超级楼梯(HDU-2040)(包含源程序).pdf”文件可能是对该算法问题的详细解析,包括问题描述、解题思路、算法流程图以及源代码注释,便于学习者理解和实现。 超级楼梯问题通常描述为:有一栋楼梯...

    算法-迷宫城堡(HDU-1269)(包含源程序).rar

    总结来说,《算法-迷宫城堡(HDU-1269)》是一道关于图论和搜索算法的编程题目,涉及到深度优先搜索、广度优先搜索以及启发式搜索算法的应用,对于提升编程思维和算法能力具有很好的实践价值。通过研究和解决此类...

    KM匹配题集

    KM 最大时,要求改动最少**、**【HDU 3523】My Brute 求 KM 最大时,要求改动最少**:这些题目中的“KM”可能不是指KMP算法,而是指Kuhn-Munkres算法(也称匈牙利算法),用于解决赋权二分图的最大匹配问题,目标是在...

Global site tag (gtag.js) - Google Analytics