文章插图
【什么是匈牙利算法】谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ >= │A│ 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为： 1．任给初始匹配M； 2．若X已饱和则结束，否则进行第3步； 3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M?E(P)，转2； 6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4； 设数组up[1..n] --- 标记二分图的上半部分的点 。down[1..n] --- 标记二分图的下半部分的点 。map[1..n，1..n] --- 表示二分图的上，下部分的点的关系 。True-相连， false---不相连 。over1[1..n]，over2[1..n] 标记上下部分的已盖点 。use[1..n，1..n] - 表示该条边是否被覆盖。首先对读入数据进行处理 ，对于一条边(x，y) ，起点进集合up，终点进集合down 。标记map中对应元素为true 。1. 寻找up中一个未盖点。2. 从该未盖点出发 ，搜索一条可行的路线 ，即由细边出发， 由细边结束， 且细粗交错的路线。3. 若找到 ，则修改该路线上的点所对应的over1，over2，use的元素 。重复步骤1 。4. 统计use中已覆盖的边的条数total，总数n减去total即为问题的解 。
推荐阅读
- DCT是什么意思
- 劲酒是不是也分很多种啊？
- “罔”的读音是什么？
- 先抹精华还是乳液
- 五十多岁的女人用什么护肤品
- 五十岁的女人适合什么护肤品
- 七老八十猜十二生肖
- 为什么我电脑上的百度文库的文档内容不显示
- 中国田径100米的记录是多少？
- 先擦水还是乳