匈牙利优化时间戳的正确性

这里来说一下匈牙利优化时间戳的正确性

附几个介绍的链接

123

开始以为(dfs)的时间戳。。。结果发现是第几次执行的时间戳。因为每次要memset一下vis数组,浪费了大量时间。时间戳巧妙地O(1)解

决了这个问题。初始化零?我只要让你数组里不管是谁都失效就好了。所以vis数组用int来存,第几次执行匈牙利算法内层的循环时间戳

就是几。设它为T。(vis!=T)的,和原来(vis=0)是等效的,即未遍历过,(vis=T)的,和原来(vis=1)是等效的,即已遍历过。每当(dfs)

下一个点。让这个点的(vis=T)。所以都不用说O(1),根本就是一个T++就解决了。

原文地址:https://www.cnblogs.com/bangdexuanyuan/p/14075141.html