poj 3041 Asteroids (二分图的最小顶点覆盖,匈牙利算法)

poj 3041题目链接
题意:一个n*n的网格中,有k个大小为1*1的小行星,现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。

思路:一个建图技巧是:对于网格图,我们可以把某个格子的横纵坐标看成点,而格子所代表的内容看成边来建图。

如果我们按照这样的方式建图,那么这道题的行或者列就成了点,而小行星就成了边。我们要做得是选最少的点,使得这些点覆盖所有的边。

根据Knoig定理,二分图的最小顶点覆盖数等于二分图的最大匹配数。

匈牙利一遍即可。1A

 

poj 1719 Shooting Contest (匈牙利算法)

poj1719题目链接

题意:射箭比赛,靶子是一个n*m的网格。网格的特点是没列只有两个白色,剩下的全是黑色。一共射m次,每列射一次,要求每行都射到至少一次才算合法,问是否有合法射法,如果有输出一组解。

思路:由于列数可能比行数多,那么我们把行编号作为左集合,列编号作为右集合,做一次匈牙利,对于每一行都找到它匹配的列,如果匹配数等于n,说明有解。对于输出一组街的问题,m列中已经匹配了n列,输出他们对应的link即可。对于剩下的m-n列,可以任意输出。由于之前不知道会剩下哪n-m列,所以在读入的时候有必要保存每一列的white格子的位置信息。

1A,有点爽。

 

 

hdu 4185 Oil Skimming (二分图最大匹配,匈牙利算法)

hdu 4185题目链接
题意:给出一个n*n的字符maze,‘.’代表水,‘#’代表油田。 挖油的机器一次会挖两个相邻方块。要求是必须两块必须都是油,不然会有杂质。问最多能挖多少次。
思路:和那道用1*2的小矩形块填充是一个思路。根据奇偶性对点标号,然后建图,匈牙利,2A. 第一遍是dfs写错了一个变量QAQ.a

 

 

hdu 1068 Girls and Boys (二分图的最大独立集,匈牙利算法)

hdu 1068题目链接
题意:有n个同学。。给出同学之间的 爱慕关系。。。选出一个集合使得集合中的人没有爱慕关系。问能选出的最大集合是多少。

思路:没有数据范围,差评!题意说得也不清楚。。由数据知道。。爱慕关系一定是相互的。。。

这道题实际上是二分图的最大独立集问题。

最大独立集问题: 在N个点的图G中选出m个点,使这m个点两两之间没有边.求m最大值

 

学到的一点是:对于二分图,可能并不能明显得分成两个不相交的集合,而是一个整体。(有左集合到又集合的边,同时有又集合到左集合的边,就是说每条边都是无相边。。?) 这其实等于把两个无向图叠加在了一起(从左指向右的和从又指向左的)

所以hungary得到的最大匹配数应该除以2,才是真正的最大匹配数。

 

 

hdu 3225 Flowers Placement (dfs+匈牙利算法剪枝,太神了)

hdu 3225题目链接

 

题意:给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行,并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案,那么输出-1.

 

思路:有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE…

想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。

比较重要的一点是。。。

n个数的某种排列,可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配

我们可以根据这个来剪枝。

具体做法:

我们先求出一个完备匹配,然后搜索每个位置能够种的花,假设当前位k置种了花i,那么判断k+1–n位置能不能形成一个完备匹配(即能否种出满足条件的花),若能那么当前位置可以种该花,继续搜索,若不能这返回

 

然后把一个false写了true.调了一个小时。。。。。。。。。。。。。。无语凝噎。

 

poj 1469 COURSES (匈牙利算法)

poj 1469 题目链接

题意:p个课程,n个学生,给出每个课程对应选取该课程的学生编号,问能否选出p个学生,使得和课程一一对应。

思路:一眼二分图最大匹配。。。需要注意的是。。两个集合可能分别给出。。建图的最大点数是两个集合的最大数目之和。。。因为没注意这个细节RE了一次。。

 

 

poj 1325 Machine Schedule(二分图的最小顶点覆盖,匈牙利算法)

poj 1325 题目链接
题意:有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组(i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启,问最少的重启次数。

 

思路:这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。

完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。

 

然后这道题就变成了二分图的最小顶点覆盖。

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

根据Knoig定理:二分图的最小顶点覆盖数等于二分图的最大匹配数。

一个证明:二分图最小顶点覆盖的证明

 

剩下的就是裸的hungary..

然而WA了好几次。。。

一个小细节没处理好。。。

由于初始是模式0.。。

所以模式0肯定要特殊考虑。。。因为初始状态是没有重启的。。。

但是我错误得以为只有当存在(i,0,0)这样的边时才忽略不算。。。

但是其实只要有一个端点是0就好了啊。。。不管哪端是0,我就用这个0来完成工作。。。依然不增加重启次数。。。

这不是什么坑点。。。脑袋秀逗了。。。

 

 

poj 1422 Air Raid (DAG的最小路径覆盖,匈牙利算法)

poj 1422题目链接

题意+思路:DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。

 

poj 2594 Treasure Exploration (DAG图最小路径覆盖变形,匈牙利算法+floyd求传递闭包)

poj 2594 题目链接

题意:一个DAG图,每个点有宝藏…可以降落任意个机器人到任意点…然后机器人可以沿着路径走,路过某个点的时候,可以取走该点的宝藏。问要取走所有宝藏,最少需要多少个机器人。

思路:乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候,可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point.

那是否还可以用最小路径覆盖做呢。。答案是可以的。。。

区别就在于一个点如果被一条路径使用过一次,还可不可以使用第二次。。。

如果我们按照传统的DAG图的最小路径覆盖考虑。。。如果一个点会被路径经过两次。。。那么我们不妨增加一个点。。。 进一步考虑。。。我们要的是尽可能覆盖所有点。。。如果这条路径前后的点不会因为这个点而中断,那么这个增设点是否存在,其实是无所谓的,只要改点前后的点连通性不受影响即可。 说到连通性,不禁想到floyd求传递闭包。

 

然后对于DAG图的最小路径覆盖问题。。。就可以用hungary算法求解。。。

ans = n – 最大匹配数。

这应该算作hungary的一个应用。

 

poj 2446 Chessboard (匈牙利算法)

poj 2446 题目链接
题意:一个n*m的矩形方格里,有k个坏点,然后问能否用1*2的矩形块将矩形方格填满。坏点不能填,小的矩形块不能重叠,不能超出边界。不能有好点没有被填。

思路:乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法(横着放,竖着放) 可能我们对于第i个,可以横着放,也可以竖着放,但是可能某种方案使得后面的某一块没办法放置,因此我们需要反过来调整第i块的放法。  这个过程似乎和二分图匹配有点类似。。?  那到底有没有相似点呢。。。又如何划分集合呢。。。?

如果每个小方格看做点,能不能填满,其实就等价与这些点的最大匹配数×2+坏点数=m*n是否成立。。。那如何划分集合呢。。。? 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是2*1的,所以容易知道,每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。

然后匈牙利搞之。

 

这题一开始WA了。。WA在没有注意到一个小细节,使得连边的时候,有的是左点指向右点,而有的连成了右点指向左点。

 

 

poj 1274 The Perfect Stall (匈牙利算法)

poj 1274题目链接

裸的匈牙利。

hdu 2063 过山车 (匈牙利算法模板题)

hdu2063题目链接

题意:求二分图最大匹配。

思路:匈牙利算法。

通过这三篇博客了解了相关概念,学习了匈牙利算法。
趣写算法系列之–匈牙利算法
二分图的最大匹配、完美匹配和匈牙利算法
匈牙利算法详解

 

感受就是:这个是相对容易学的算法。。并没有名字那么不明觉厉。。。

主体就是一个dfs的过程。。。。

不过据说有比较多的应用。

所以打算切一些题目加深理解以后再回来总结。

 

 

 

uva 10986 Sending email (spfa)

uva10986题目链接
题意:裸的spfa.

思路:模板,1A.

 

poj 2949 Word Rings (spfa+栈优化)

poj2949 题目链接
题意:我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字
母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相
匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。
我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算)
我们想要使这个环串的平均长度最长。

思路:参考了国家集训队论文《spfa算法的优化与应用》

首先我卡在了关于接龙问题的处理方法,只能想到n^2的方法。。显然gg.

而正解是把每个单词看做一条边,把每个单词开头的两个字母和结尾两个字母看做起点和终点,由于都是小写字母,2位26进制数最多表示26*26。

这个建图方式并不是特别显然,不过想一下还是可以理解的。。以及这应该算是处理单词接龙问题的一个技巧。。。

 

这道题综合了两种常见的问题:字符串的接龙以及平均值的最优化问题。对于前者,我们可以采取把单词看成边,把首尾字母组合看成点的方法。例如对于单词ababc就是点”ab”向点”bc”连一条长度为5的边。这样问题的模型变得更加清晰,规模也得到减小。那么原问题就可以转化成在此图中找一个环,使得环上边权的平均值最大。对于这种问题,我们有很经典的解决方法:

由于Average=(E1+E2+…..+Ek)/K
所以Average*K=E1+E2+……+Ek
即(E1-Average)+(E2-Average)+….+ (Ek-Average)=0
另外注意到上式中的等于号可以改写为小于等于,那么我们可以二分答案Ans,然后判断是否存在一组解满足(E1+E2+…..+Ek)/K>Ans,即判断
(E1- Ans)+(E2- Ans)+….+ (Ek- Ans)>0
于是在二分答案后,我们把边的权值更新,问题就变成了查找图中是否存在一个正环。

 

然后参考了这篇题解学习了一下栈优化的spfa: spfa栈优化   

以及这篇博客中比较了dfs的spfa和普通栈优化的spfa… 200+ms vs 2000+ms…十倍的优化。。太神了。。。

 

/*
枚举每一个平均长度mid值。
如果存在一个环,(E1+…+Ek)/k>=mid(其中k是边数,E1……Ek是各个边权),
那么正解比mid大,否则比mid小,这就是二分策略。
那么怎样知道是否存在(E1+…+Ek)/k>=mid 呢?
如下转化:(E1+…+Ek)>=mid*k
E1-mid + E2–mid + E3-mid + … + Ek-mid >= 0
所以,把所有的边权改为Ei – mid,然后看是否存在正环就可以,存在就是满足条件。
*/

 

 

poj 1860 Currency Exchange (spfa求最长路)

poj 1860 题目链接

题意:有n种货币,m个货币交易点,每个货币交易点只能是两种货币之间交换,给出两个方向的汇率和手续费。初始拥有数量v的货币s,问能否经过一些py交易,使得最后手里的货币s比v多。

思路:大概还是用spfa求最长路。。松弛那里需要注意一下算法。。。

1A。。。好爽啊。。。。。