KM演算法的時間複雜度是O(n^3)還是O(n^2*m)？（n是點數，m是邊數）

網路上的各種資料博客都說KM演算法的時間複雜度是O(n^3)的。然而KM演算法要找O(n)次增廣路，每次找增廣路最多需要修改O(n)次頂標，而每次修改頂標都要進行一次類似於匈牙利演算法的DFS，每次匈牙利演算法最壞情況是O(m)的，這樣KM演算法的最壞情況應該是O(n^2*m)的。

而且的確可以找到卡掉KM演算法的數據：400*2個點，對於每個左邊的點i和右邊的點j連一條權值為(i+j-2)^2的邊。我嘗試了幾個網上的代碼，都跑到了60秒以上。我用一個變數cnt作計數器，統計循環的次數，最終cnt為4330799200。

我猜測，由於除了給定的m條邊，其他邊的權值都是0，那麼這些權值為0的邊被訪問的次數會不會是O(n)的，給定權值的邊會被訪問O(n^2)次，那麼最終的複雜度就是O(n^2*m+n^3)。

1. 你說得都對。

事實上，KM 確實是可以 $O(n^3)$ 的實現的，確實每個點需要修改 $O(n)$ 次頂標不假，但是你有沒有發現每次修改頂標之後相等子圖變大了？也就是說，這 $O(n)$ 次頂標修改的 bfs 可以合在一起變成 $O(m)$ 的。

---