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.调了一个小时。。。。。。。。。。。。。。无语凝噎。