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

hdu 3523 题目链接

 

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

 

思路:妈蛋,什么鬼题面。。。看不懂。。。然后看了题解。。。知道了题意。。

的的确确做过相当类似的一道呢。

先n*n*n的复杂度(1E6)处理权值,然后KM.

1A.

 

 

 

 

hdu 3315 My Brute (二分图最佳匹配,KM算法)

hdu3315 题目链接

题意:两个人分别各有n个怪物。进行n场pk.每只怪物必须恰好进行一场pk.如果先手的第i只怪物赢,会获得v[i]的val,输会减少v[i]的val.给出两个人n只怪物的血量和攻击力。先手的初始战斗顺序为1,2,3..n(后手的战斗顺序一直都是1,2,3..n) 现在问能否通过调整顺序使得先手获得的val最大,如果这个val大于0,表示先手可以赢。如果可以赢,那么还要求调整后的顺序和原始顺序的相似度,并且使得相似度尽可能大(If there are multiple orders, you should choose the one whose order changes the least from the original one)

 

思路:先根据血量和攻击力,n*n的时间处理出每场战斗的输赢信息,然后结合v[i],得到每两个怪物战斗的先手得到的val的值。

然后和hdu 1853类似,依然希望尽可能多的安排不改变。

我们的做法仍然是把w*N,然后钦定的w再+1

然后改变个数,由于存在负数。。。和hdu 1853的处理有区别。。。

想了一下。。。其实用link数组对照初始钦定顺序就好了啊。。。

1A.爽上天。。。

最近各种1A…?好开心。

 

选区_075

 

 

 

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

hdu 2853题目链接

题意:n个公司,m个任务(m>=n),一个公司只能对应一个任务,一个任务也只能对应一个公司。给出一个n*m的mat,表示每个公司对应每个任务产生的val。  然后给出n个数,表示初始钦定(雾)这n个公司分别做哪些任务。 但是可能初始的安排得到的val表示最大的。我们现在想得到最大的val,并且保证改变的安排数最少。求安排后得到的 val比初始安排大多少,以及需要改变的安排数量。

思路:最大val很好求,KM就好。。。但是,怎么才能保证改变的安排数最少呢? 尤其是当两个安排val一样的时候,如何才能保证优先选已经安排好的,而不取选另一个呢?

并没有想出来,看了题解T T

太神辣。

由于KM算法会根据权值来选取,权值大的会优先。

如果我们把每个权值*k(k>n),然后对于已经钦定的安排,每个权值再+1.

这样,钦定的安排就会有更高的优先级,最后统计的时候除以k,那么权值答案不会有影响(利用到了初等数论的整除知识。。。?)

然后这样做该有一个好处。

不除以k的权值和再模k,就是没有改变的安排数。

原因是由于没有钦定的安排的权值每个都乘了k,最后%k都为0,只有那些钦定的安排每个会贡献1.

又由于k>n,这样就保证了正确性。

 

这做法太神了。。。。。吓傻了。。。。

我试着推广一下。。。?

对于根据权值来决定优先顺序,但是权值相同的时候还是需要对一些赋有更高的优先权的模型。。。?

除了再增加一维的大家都能想到的做法。。。这样的做法是不是有通用性呢。。。?

做法太神,我得慢慢体会。。

 

 

 

 

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

hdu2448 题目链接

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

思路:想到了用floyd先更新一下距离,然后KM.不过思维不够严谨,只更新了港口通过油田到达油田的距离,而没有更新油田通过油田到达油田的距离QAQ.

所以应该先更新油田通过油田到达油田的距离,然后再更新港口通过油田到达油田的距离。。。

哦,还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n,这样写KM里会比较好写。。。不然总得带着那个id[i].

 

选区_074

 

 

 

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

hdu 3718题目链接

题意:东西分类作业,有n个东西,k组,m个学生,不同种类的东西用不同的字母表示,相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同,但是字母只是一个标号(But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ) 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

思路:用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生,o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从而得到正确率。 因为一个map忘记每次清空,WA了一次。。。2A..

 

 

 

hdu 3722 Card Game (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 3722题目链接

题意:n个串,a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。

思路:先暴力处理出每两个的权值。。200*200*1000的复杂度。。还是可以接受的。。

然后把每个串看成了一个点,由于一个串最多可以被放在前面一次,被放在后面一次,所以可以类比图论中的环的入度和出度为1.

然后跑一遍KM. 1A,开心。

 

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

hdu 3435题目链接

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

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

选区_073

 

做法同hdu 1853…

 

 

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

hdu 1853 题目链接

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

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

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

正确性:

对于满足条件的环,每个点的入度和出度均为1,我们可以把每个点拆成入点和出点,那么也就是说一个入点对应一个出点,反之亦然,那么这个问题就变成了一个二分图匹配问题,

 

然后这道题有重边,2A.

又一次体会到了拆点的神奇。。。这个大概算是需要慢慢积累的技巧吧。。像辅助线一样的。。。

还有体会到了环的模型竟然也可以转化成二分图匹配,真是厉害==

 

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

hdu 2813 题目链接

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

思路:裸的KM。 用map把武将名字变成点的编号。

 

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

hdu 2282 题目链接

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

思路:先记录每块巧克力的位置,为了之后算w,然后将巧克力和盒子分别看做X,Y集合。。。建图。 然后KM   。。1A

 

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

hdu 3395题目链接

题意:鱼,一些鱼认为自己是汉子,然后他会去和他认为是妹子的鱼啪啪啪,然后被啪啪啪的妹子就会产卵? 卵的val是它parent的val的异或。给出n,为鱼的数量,然后给出一个n*n的 mat,a[i][j]==1表示第i条鱼认为第j条鱼是妹子。问卵的最大val之和是多少。需要注意的是:每条鱼最多可以去和一个妹子啪,并且可以作为妹子被啪一次(这两个是独立的。。。) (Each fish can attack one other fish and can only be attacked once)

 

思路:二分图最佳匹配,KM算法,2A.

 

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

hdu 2426 题目链接

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

 

思路:二分图最佳匹配。。。读漏题QAQ. 原来分数为负的房间是不能住的啊。。。。

考虑无解的情况,如果学生数比宿舍数多,无解。

如果一个学生不喜欢任何宿舍或者没给任何宿舍打分,无解。

然后KM.

 

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

hdu 1533 题目链接

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

思路:有了那两个条件,这题就是赤裸的二分图最优匹配了。建图也很easy.可以预处理下w,就是两点的哈密顿距离.

需要注意的是这道题求的是最小权值。那么做法就是将w取负,然后答案再次取负即可

(还有其他方法处理,不过这种最easy应该?)

(不过要保证初始化某些数组的时候要比所有的值小,所以不能是0,而应该是-inf)

以及:初始化数组为-inf的方法,可以memset(lx,0xc0,sizeof(lx));

这样得到的-inf只和inf的绝对值差1,好评如潮。

0xc0,0xc0,0xc0,重要的常数说三遍

 

哦还有,不要忘记在每次find的时候记录X集合中的点,这是比hungary算法的find里多的一个步骤,并且是容易忘记的。。。