KM算法总结

km算法我的理解

 

刷了不到20道题。。。回来总结一发。。

如果题目求的是最小权值匹配,比较好的做法是将权值取取值,最后res再取负就好。需要注意的是初始化的时候w和lx要比所有值都小,所以要ms(lx,0xc0)

最正确解最小权匹配的办法是用一个很大的数-当前边[……]

Read more

HDU 3523 Image copy detection (二分图最佳匹配,KM算法,题意杀)

hdu 3523 题目链接

 

题意:有m个排列,每个排列有n个,然后要找一个长度为n的排列(1..n每个数字恰好出现一次),使得这个排列到其他m个排列的距离之和最小。 两个排列之间的距离是对应位置上数字差的绝对值的和。

 

思路:妈蛋,什么鬼题面。。。看[……]

Read more

hdu 2853 Assignment (二分图最佳匹配,KM算法+数论,做法太神)

hdu 2853题目链接

题意:n个公司,m个任务(m>=n),一个公司只能对应一个任务,一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。  然后给出n个数,表示初始钦定(雾)这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。[……]

Read more

hdu 2448 Mining Station on the Sea (floyd+KM)

hdu2448 题目链接

题意:n个船n个港口,一个港口只能承接一个船,m个油田,给出n个船各自在哪个油田,然后给出m个油田之间的无相图,然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。

思路:想到了用floyd先更新一下距离,然后KM.不过思维不够严谨,只更新了港口通过[……]

Read more

hdu 3718 Similarity (二分图最优匹配,KM算法)

hdu 3718题目链接

题意:东西分类作业,有n个东西,k组,m个学生,不同种类的东西用不同的字母表示,相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同,但是字母只是一个标号(But the LABEL of group doesn’t make sense[……]

Read more

hdu 3435 A new Graph Game (有向环覆盖,拆点,二分图最优匹配,KM算法)

hdu 3435题目链接

题意:给你一张图,图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值

思路:题意杀啊。。。什么鬼了。。。然后时间。。1000的数据。。n3复杂度。。。还多组数据。。。。不是很懂这个时间是怎么算的。。为毛才2600MS啊。。。。

选区_073

&n[……]

Read more

hdu 1853 Cyclic Tour (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 1853 题目链接

题意:一个带权有向图,要求找出若干的环,满足每个点恰好在一个环里,并且环的权值和最小……问最小权值和。

思路:没有思路,不知道怎么处理环的问题。于是去群里问了下。正确做法是拆点

如果有一条边i->j,那么就连一条i->j’的边。

正确[……]

Read more

hdu 2813 One fihgt one (二分图最优匹配,KM算法)

hdu 2813 题目链接

题意:吕布有n个武将,曹操有m(m>=n)个武将。给出k个关系,为吕布的某个武将和曹操的某个武将pk后会受到的伤害。吕布要求他所有n的武将都要上场,每个武将只能战斗一次,问如何安排,使得所有武将受到的伤害总和最小。

思路:裸的KM。 用map把武将名字变[……]

Read more

hdu 2282 Chocolate (二分图最优匹配,KM算法)

hdu 2282 题目链接

题意:n个盒子围成一个圈,给出n个盒子中每个盒子中的巧克力个数,巧克力的总数不超过n,从一个盒子中移动一块巧克力到相邻的盒子里称为one “move”,(由于围成一个圈,所以第1个和第n个盒子也是相邻的) 问最小的移动“move”数,使得每个盒子里最多有一快巧克力。[……]

Read more

hdu 3395 Special Fish (二分图最佳匹配,KM算法)

hdu 3395题目链接

题意:鱼,一些鱼认为自己是汉子,然后他会去和他认为是妹子的鱼啪啪啪,然后被啪啪啪的妹子就会产卵? 卵的val是它parent的val的异或。给出n,为鱼的数量,然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少[……]

Read more

hdu 2426 Interesting Housing Problem (二分图最佳匹配,km算法)

hdu 2426 题目链接

题意:n个学生,m个宿舍,每个学生住一个宿舍,然后n个学生给若干个宿舍打分,分数可正可0可负,学生不能住打的分为负的宿舍,或者没有打分的宿舍。问在满足上述条件的前提下,所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

 

思路:二分图最[……]

Read more

hdu 1533 Going Home (二分图最佳匹配,KM算法)

hdu 1533 题目链接

题意:给出一个n*m的maze,其中包含不超过一个人(用m表示),以及和人数相等的房子(用H表示),其他都是‘.’,表示可以经过的路径。人向一个方向移动花费代价1.问每个人都回到一个房子里的最小代价是多少。ps:每个格子是无限大的,也就是所有人可以同时踩在一个格子里[……]

Read more

hdu 2255 奔小康赚大钱 (二分图最佳匹配,KM算法模板题)

hdu 2255 题目链接

 

题意:传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革:重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住(如果有老百姓没房子住的话,容易引起不安定因素),每家必须[……]

Read more