关于匈牙利算法的小结
二分图定义：
两个非空集合A, B A与B没有交集，同一集合内部没有连边，这个图为二分图，A为左部，B为右部。
判定：
二分图不存在奇环。
用染色法即可。
二分图最大匹配
二分图没有增广路时，就是最大匹配。
特点：当一个点成为匹配点后，至多找到增广路更换匹配对象，但是绝不会变回非匹配点。
时间复杂度 (O(nm))
匈牙利算法代码框架(模板)
只用从左向右建单向边！！
建议使用vector
题目 && 模型
Round1
1.棋盘覆盖
二分图匹配的0/1要素：
-
0要素：点能分成两个独立的集合，每个集合内部没有边
-
1要素：每个点只能有一条匹配边相连
这题将骨牌看做边，格子看做点，建模。
同类题: 車的放置
2.导弹防御塔
二分图多重匹配，拆点，或使用网络流，一般使用网络流。
3.二分图带权匹配
网络流吧。
Round2
1. 二分图最小点覆盖Machine Schedule
定理：二分图最小点覆盖=最大匹配边数。
模型特点：每条边有两个端点，两者至少选一个
同类题Muddy Fields， POJ3041
2. 二分图最大独立集骑士放置
定理：二分图最大独立集＝节点数－最大匹配数
3. ({ m DAG})最小路径点覆盖
给一个 ({ m DAG}) ，要求用尽量少的不相交的简单的路径，覆盖 ({ m DAG}) 的所有顶点。
定理：({ m DAG})的最小路径点覆盖包含的路径条数 = 点数 - 拆点二分图最大匹配数
拆点二分图：设 ({ m DAG}) 为 ({ m G=(V,E)})，拆点二分图为 ({ m G'=(V',E')}) 将G中的每一个点 (x) 拆成左部节点 (x) 与右部节点 (x+n) , 对于 ({ m E(x, y)}) 在 ({ m G'}) 中连单向边 ({ m E'(x, y + n)}) , 得到的 ({ m G'}) 就是拆点二分图。
Round3
1.[SCOI2010]连续攻击游戏
每个集合只能选一个元素的模型
2.[ZJOI2007]矩阵游戏
棋盘模型
3.[NOI2009]变换序列
匈牙利算法的本质
4.[HNOI2013]消毒
枚举 + 最小点覆盖模型
5.[SHOI2001]小狗散步
“Pandog每次与主人相遇之前最多只去一个景点”， 建立二分图最大匹配的关键信息
省选之前就写这么多了。