何の話かと言うと atcoder.jpこの問題、公式解説では、最小カット問題（＝最大フロー問題）に帰着して、Dinic 法で解くという解法が紹介されていますが、もうちょっと素朴な「ナップサック問題」としても解ける（解けた）ので紹介します。 ナップサック問題…