同一の強連結成分内の落とし物は、最初に訪れた時点で全て拾えばよいです。よって、各強連結成分を一つにまとめることで、グラフは DAG であると仮定できます。

以下では、グラフは DAG であり、頂点 \(1, 2, \dots, N\) がトポロジカル順に並んでいると仮定します。解くべき問題は、最小費用流問題に帰着することができます。

まず思いつくのは、次のようにする方法でしょう :

• \(1 \leq u \leq N\) に対し頂点 \(\mathrm{in}_u, \mathrm{out}_u\) を用意する。また、始点と終点として頂点 \(S, T\) を用意する。
• \(1 \leq u \leq N\) に対し、\(\mathrm{in}_u\) から \(\mathrm{out}_u\) に容量 \(1\)、コスト \(-X_u\) の辺と容量 \(\infty\)、コスト \(0\) の辺を張る。
• 各辺 \((u, v)\) に対し、\(\mathrm{out}_u\) から \(\mathrm{in}_v\) に容量 \(\infty\)、コスト \(0\) の辺を張る。
• \(S\) から \(\mathrm{in}_1\) に容量 \(\infty\)、コスト \(0\) の辺を張る。
• \(1 \leq u \leq N\) に対し、\(\mathrm{out}_u\) から \(T\) へ容量 \(\infty\)、コスト \(0\) の辺を張る。
• \(S\) から \(T\) へ流量 \(K\) 流すときの最小コストを \(-1\) 倍したものが答えである。

ただし、この方法だとコストが負の辺が生じてしまいます。 次のようにすることで、負辺を除去することができます。

• \(1 \leq u \leq N\) に対し、\(\mathrm{in}_u\) から \(\mathrm{out}_u\) に容量 \(1\)、コスト \(0\) の辺と容量 \(\infty\)、コスト \(X_u\) の辺を張る。
• 各辺 \((u, v)\) に対し、\(\mathrm{out}_u\) から \(\mathrm{in}_v\) に容量 \(\infty\)、コスト \(X_{u + 1} + \dots + X_{v - 1}\) の辺を張る。
• \(S\) から \(\mathrm{in}_1\) に容量 \(\infty\)、コスト \(0\) の辺を張る。
• \(1 \leq u \leq N\) に対し、\(\mathrm{out}_u\) から \(T\) へ容量 \(\infty\)、コスト \(X_{u + 1} + \dots + X_N\) の辺を張る。
• \(K \left(\sum_u X_u \right)\) から、\(S\) から \(T\) へ流量 \(K\) 流すときの最小コストを引いたものが答えである。

実装例 (C++)