最小費用流 1 回で解けます．方針は kyopro_friends さんの解説と同じです．

数 \(1\) をできるだけ使わないようにしながらフローを流し，最後に残った \(1\) を使って \(1+1=2\) を作ればよいので，\(S\to 1\) の辺のコストを \(1\) ，それ以外の辺のコストを \(0\) にして最小費用流を考えればよいです．使える \(1\) の個数を \(C\)，流量を \(F\)，コストを \(\rm{cost}\) として求める答えは \(F+(C-\rm{cost})/2\) です．

計算量は \(O(FN^2\log N)\) と非常に大きいですが，実際には高速に動作しました ( pypy で 300ms 程度)．