hdu 3225题目链接 题意：给出一个n*m的矩阵。每个格子有一个数。每行1..n必须每个出现一次。每列1..n每个数最多出现一次。现在要添加一行，并且补违反上述规则。问添加的方案中字典序第k小的方案。如果一共不足k种方案，那么输出-1. 思路：有点像八皇后。。。就是纯搜。。。不过n好大。。。这么搜会TLE... 想了半天也没思路。。。看了题解。。发现是用二分图匹配来剪枝。。 比较重要的一点是。。。 n个数的某种排列，可以看做是一个位置集合{1..n}和数字集合{1..n}的二分图最大匹配。 我们可以根据这个来剪枝。 具体做法： **我们先求出一个完备匹配，然后搜索每个位置能够种的花，假设当前位k置种了花i,那么判断k+1--n位 …

poj 1325 题目链接 题意：有两台机器A和B,分别有n和m种工作模式。 现在有k个job,三元组（i,x,y),job i可以用A机器的x模式完成或者用B机器的y模式完成。初始两个机器都在模式0.机器更换模式的时候需要重启，问最少的重启次数。 思路：这道题的难点在于建图。。。每个job恰好对应了两种模式。。那么如果把模式看成点。。边就对应了这个job。。这样就是一个二分图。。。至于方向。。。怎么指都可以。。。统一就行。。 完全没有图的影子的题依然可以用图论解决。。。而且算是加深了对图这种模型的理解把。 然后这道题就变成了二分图的最小顶点覆盖。 **二分图中，选取最少的点数，使这些点和所有的边都有关联（把所有的边的覆盖），叫做最 …

poj 1274题目链接 裸的匈牙利。 /* *********************************************** Author :111qqz Created Time :2016年05月25日 星期三 17时49分22秒 File Name :code/poj/1274.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include …

hdu2063题目链接 题意：求二分图最大匹配。 思路：匈牙利算法。 通过这三篇博客了解了相关概念，学习了匈牙利算法。 趣写算法系列之--匈牙利算法 二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法详解 感受就是：这个是相对容易学的算法。。并没有名字那么不明觉厉。。。 主体就是一个dfs的过程。。。。 不过据说有比较多的应用。 所以打算切一些题目加深理解以后再回来总结。 /* *********************************************** Author :111qqz Created Time :2016年05月25日 星期三 16时51分32秒 File Name …