数 \(1\) の個数が \(0\) の場合を考えます。

このとき、操作が出来るペアの間に辺を貼ると、辺は偶数と奇数の間にしか貼られないので二部グラフになります。そのため、最大流で答えを求めることが出来ます。

一般の場合を考えます。 \(1\) を \(2\) つ消す操作が出来るので、単純な最大流では答えを求められません。

\(1+1=2\) として消す回数を \(k\) と固定し、残りの \(1\) は偶数とペアにして操作をすると決めます。このとき、偶数と奇数をペアにして消せる回数を \(f(k)\) と置きます。操作回数の合計は \(f(k)+k\) です。

ここで、\(f(k)+k\) が上凸なことが示せれば、\(0\) を左端、\(1\) の個数を \(x\) として \(\lfloor \frac{x}{2}\rfloor\) を右端とする三分探索によりこの問題に答えることが出来ます。

\(f(k-1)-f(k)\leq f(k)-f(k+1)\) であることが示せます。これは、背理法を用いるとよいです。(\(f(k-1)-f(k)> f(k)-f(k+1)\) だとすると、\(k\) のときに最大マッチングであることと矛盾します。)

よって \(f(k)\) は上凸で、\(g(k):=k\) も上凸なので、上凸な関数の和である \(f(k)+k\) も上凸です。よってこの問題に答えることが出来ました。

また、三分探索が不要な解法もあります。

\(f(k)\) の取る値を考えると、\(1\) の個数が増えて最大マッチングが減少することはありえないこと、また最大マッチングは高々新たな \(1\) の個数しか増加しないので、\(f(k)\) は \(f(k+1)\) 以上 \(f(k+1)+2\) 以下であることがわかります。

上凸性と合わせると、\(f(k)+k\) で隣接項について差分を取ると \(+1,\ldots,+1,0,\ldots,0,-1,\ldots,-1\) となっていることがわかります。（\(+1,0,-1\) はそれぞれ存在しない場合もあります。）

このことから、左端と右端の \(f(k)+k\) の値を求めると、最大値を取る \(k\) の値を一つ求めることができます。

よって三分探索を用いず \(3\) 回の最大流により答えを求められます。

実装例(c++)