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

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

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

Read more

poj 1719 Shooting Contest (匈牙利算法)

poj1719题目链接

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

思路:由于列数可能比行数多,那么我们把行编号作为左集合,列编号作为右集合,做一次匈牙[……]

Read more

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

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

Read more

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

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

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

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

最大独立集问[……]

Read more

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

hdu 3225题目链接

 

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

 

思路:[……]

Read more

poj 1469 COURSES (匈牙利算法)

poj 1469 题目链接

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

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

Read more

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

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

 

思路:这道题的难点在于[……]

Read more

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

poj 1422题目链接

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

 

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

poj 2594 题目链接

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

思路:乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过[……]

Read more

poj 2446 Chessboard (匈牙利算法)

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

思路:乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法(横着放,竖着放) 可能我们对于第i个,可以[……]

Read more

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

poj 1274题目链接

裸的匈牙利。

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

hdu2063题目链接

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

思路:匈牙利算法。

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

 

感受就是:这个是相对容易学的算法。。并没有名[……]

Read more