想定解は\(O(NM + N^3 d \log N)\)ですが、\(O(NM + N^3 d)\)で解くことも可能です。

想定解と同様の議論により、この問題は次の問題を\(d\)回解くことに帰着できます(二分探索を行わないことに注意してください)

\((N^2, N)\)頂点の二部グラフが与えられる。辺は最初\(0\)本である。ここに、\(N^2\)本の辺が順々に追加されていく。初めて最大マッチングが\(N\)となるタイミングを求めよ。

まず、この問題は\(O(N^4)\)で解くことが可能です。最大流問題として捉え、辺を追加するたびに増加路がないかを\(O(V + E)\), つまり\(O(N^2)\)で探索すればよいです。実際に、「始点Sから終点Tまでパスが存在するか(復元付き)dfsを行い、発見したらそのパスにそって流す」という操作を行えばよいです。

上記のアルゴリズムを高速化します。増加路が発見できない間、始点Sから到達可能な頂点集合、というのは単調に増加していくことに注目します。つまり、増加路が発見できなかったならば、次のdfsを最初から行う必要はありません。

このアイデアにより、上記の問題は \(O(流量 \times (V + E)) = O(N^3)\)で解くことができます。