传送门：【HDU】2389 Rain on your Parade 题目分析： 这题目非要我学Hopcroft-Krap= =||。。普通的DFS版的二分匹配不行，最大流又爆内存。。不得不学更好的算法了。 二分匹配的其他性质我也不多说了，不会的自行搜索，网上很多的。 现在我主要对该算法的实现发表一下自己的见解。（算法复杂度的证明不会，论文没看太懂） 该算法的核心思想是通过bfs寻找

http://blog.csdn.net/u011742541/article/details/14104573 //Hopcroft-Karp算法 有点类似dinic 都是先对图BFS分层再沿层数DFS找增广路 //***************************************************************************

子集构造算法： 因为NFA不适合直接用来做词法分析器的识别，是因为它的状态转移是不确定的，这种情况下写一个算法往往需要回溯，对于分析的效率影响会比较大，所以需要用子集构造算法由NFA将它转换成与它等价的DFA(因为DFA是确定有限状态自动机)，最终转换成词法分析器可以使用的代码。 子集构造算法思想： a(b|c)* 下图是一个NFA，很明显它的转移边包含 ε 所以它的状态转移是不确定的,我们所要