文件名称:匈牙利算法——基本步骤-(HDUACM2010版_13)二分匹配及其应用
文件大小:339KB
文件格式:PPT
更新时间:2024-05-13 11:06:49
杭电ACM课件 ACM
匈牙利算法——基本步骤: 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;