E. Fair Share - Codeforces Round #770 (Div. 2)

解けなかった...フローというかグラフ系が見えない事が多い。

------------------------------------------------------------

問題

M個の偶数長の整数配列が与えられる

それぞれの整数にL, Rを割り振り方で、以下を満たすものを一つ構築せよ。ない場合は-1を出力

・各配列についてL, Rの個数は同じである

・全てのLからなる多重集合とRからなる多重集合は等しい

------------------------------------------------------------

解法

同じ数字が半分にL, Rに分けられる必要があり

配列内が半分にL, Rに分けられる必要がある等

半分という条件が多い。

とりあえずグラフで扱う事を思いついたとして。

配列ごとの小問題を並列に扱いたいため

各配列のインデックスから存在する数字に、存在する個数分だけ辺を貼った2部グラフを考える。

すると各辺にL, Rを割り振る問題と言い換える事が出来る。

この時、配列から出ている辺の半分がLであり

各数字から出ている辺の半分がL,になれば良い。

これはオイラー路について、辺の向きによって割り振れば条件を満たす。

---------------------------------------------

実装について

同じ辺を複数回見ると計算量がおかしくなるため

各頂点iについて自分が何本目の辺までを見たかをpos[i]のように管理する。

バックトラックは起こらないため

以後はpos[i]以下の辺だけを見ればよく

pos[i]を使ったらpos[i]++とする。

また、各辺について逆辺のインデックスを持ち

auto[t, rev] = g[i][pos[i]];
if (t == -1) {
    pos[i]++;
    continue;
}
g[t][rev].fi = -1, g[i][pos[i]].fi = -1;

のように使った辺の逆辺の行き先を-1等にすることで

むこうで見た時に間違って使わないようにする

（削除した辺が向こうで見られるのは一回だけなので計算量は問題ない）

バイトの競プロメモ