ABC393-G 解説 と同様に費用流双対を用いた解法を簡単に解説します。

二分探索を行います。 \(1-N\) 最短路長が \(D\) を達成できるような最小の辺数を求める問題を考えると、次の LP として記述できます。

\[ \begin{aligned} &\min. & & \sum_e w_e \\ &\mathrm{s.t.} & &x_v - x_u \leq w_e & & (\forall e = (u,v)) \\ & & &x_N - x_1 \geq D \\ & & &0 \leq w_e \leq 1 & &(\forall e = (u,v)) \end{aligned} \]

この LP の双対を取ると、次の最小費用循環流問題の答えを \(-1\) 倍したものになります。ここから主問題の解の整数性も確認できます。

頂点 \(1, 2, \dots, N\) を用意する。次のように辺を貼った時の最小費用循環流のコストは？

• 頂点 \(u\) から頂点 \(v\) に容量 \(1\) 、コスト \(0\) の辺を貼る。
• 頂点 \(u\) から頂点 \(v\) に容量 \(\infty\) 、コスト \(1\) の辺を貼る。
• 頂点 \(N\) から頂点 \(1\) に容量 \(\infty\) 、コスト \(-D\) の辺を貼る。

よってこの費用流問題を実装することで問題を解くことが出来ました。(このままだと流量が \(\infty\) となるため ACL の最小費用流を用いる場合は計算量の理論保証のために問題を少し変形する必要があります。)
計算量は適切に計算量改善を行うと ACL の最小費用流を用いても \(\mathrm{O}(M(N+M) \log (N+M))\) で済み十分高速です。(ヒント：ACL の slope 関数を用いることになります)

• 類題 : AOJ2230: How to Create a Good Game, ucup 2-11 E: Existing Distance など