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

hdu 3225题目链接

 

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

 

思路:[……]

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 1274 The Perfect Stall (匈牙利算法)

poj 1274题目链接

裸的匈牙利。

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

hdu2063题目链接

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

思路:匈牙利算法。

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

 

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

Read more