算法合集之浅析二分图匹配在信息学竞赛中应用.ppt

复杂度分析 下面来分析一下该算法的时间复杂度 算法中执行了如下操作 3> 更新 M' O ( n ) 2> 询问是否存在 q 的某个邻结点 p 为可匹配点 O ( mn )= O ( n 3 ) 1> 将所有 Y' 结点按权值大小非降序排列 O ( mlog 2 m ) = O ( n 2 log 2 n ) 4> 更新 R 以及 Path ; O ( n 3 ) 复杂度分析 前三个操作复杂度都显