【匈牙利算法】有没有人能告诉我什么是匈牙利算法怎么个算法...我要做运筹学作业...

【匈牙利算法】有没有人能告诉我什么是匈牙利算法怎么个算法...我要做运筹学作业...

【答案】 谈匈牙利算法自然避不开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即为问题的解.

我也是这个答案