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

poj 1274题目链接

裸的匈牙利。

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

hdu2063题目链接

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

思路:匈牙利算法。

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

 

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

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

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

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