このまま問題の答えを考えるのは非常に難しそうです。なので、二分探索を行います。

二分探索をするには、以下の問題が解ければよいことになります。

問題文に書かれている操作を $N$ 回行う。しかし、全ての操作のコストは $X$ 以下である必要がある。$N$ 回の操作を全て行うことは可能か？

ここで、重要な性質があります。それは、ある段階で操作したときにコストが \(X\) 以下となる頂点はその後ずっとコストが \(X\) 以下であるということです。

なので、以下の貪欲法をすることで上記の問題を解くことができます

• stack $s$ を持つ。始め $s$ は空である。
• はじめの時点で操作してもいい頂点を全て $s$ に入れる。
• $s$ が空でない限り、以下の操作を繰り返し行う。
• $s$ から頂点を $1$ 個取り、これを $v$ とする。$s$ から $v$ を削除する。
• また消されていない頂点に対して、操作にかかるコストを $A_v$ 減らす。
• 上の操作により、操作してもコストが $X$ 以下となった頂点を $s$ に入れる。
• 上記の操作を行い、全ての頂点を削除することができれば可能、そうでなければ不可能です。

よって、上記の問題を \(O(\log(N \times \max A))\) 回解くことによって元の問題の解を得ることができます。

計算量は \(\mathrm{O}((N+M)\log(N \times \max A))\) です。