https://atcoder.jp/contests/past202109-open/tasks/past202109_k

前提知識

解説

https://atcoder.jp/contests/past202109-open/submissions/26707534

慣れていると、この問題がかなりフロー系で解けるのではないかという感じに思えてくる。
理由としてははっきり言えないのだが、

ペアを作る、マッチングをするような問題である
総和の最大値を求める
結構微妙な制約

みたいな所からフロー感が漂う。
コストが含まれるので最小費用流で考えていくと解ける。

なお、今回の問題はよりストレートに重み付き二部グラフ上での最大マッチングとして定式化できる。
やってることは変わらないような気もするが、自分は最小費用流の延長戦上として解いた。

最小費用流

もし、最小費用流について知らない場合はどこかで調べてこよう。
最小費用流は名の通り最小値を求めるアルゴリズムであるので、入門としては最小値を求めるような問題がいいだろう。
他の問題を入門として選ぶことを勧める。

さて、理解はできているものとして話を進めていこう。

「選択」を分岐で表現する

さて、選択を作っていく。
グラフは

始点と終点
オスpを表す頂点
メスqを表す頂点

のP+Q+2頂点を用意しよう。
ここでオスpとメスqがつがいになる場合は、

始点→オスp→メスq→終点

の経路で流量1だけ流れるという風に定義しよう。

(流量,コスト)
始点-(1,0)→オスp-(1,A[p]+C[q])→メスq-(1,0)→終点

という感じである。
逆につがいにならなかった場合は、その2匹間に流れないので、

始点-(1,B[p]+D[q])→終点

ということになる。これをすべてのペアについて作っていけばいいのだが、そうすると、
始点と終点の間に複数の辺で複数のコストのものが出来上がってしまう。
これでは、うまく選択されていないペアの所に流量を流すことができなくなってしまう。
ここで1工夫加えよう。

全部選択してないことをベースに考える。

選択によって幸福度を変化させるのではなく、すべてのオスとメスは最初は含まれない状態から始めて、
つがいを作ると、そのオスとメスの幸福度が変化するという風に考えることにしよう。

より具体的には、最初は幸福度はBの総和とDの総和ということにしておく。
そして、オスpとメスqがつがいになったとしたら、幸福度が+(A[p] - B[p] + C[q] - D[q])されるということにしておく。
こうすることで選択としては、つがいにならないなら幸福度は+0だし、
つがいになったら+(A[p] - B[p] + C[q] - D[q])されることになる。

フローとして考えると、オスpとメスqがつがいになるなら

始点-(1,0)→オスp-(1,(A[p] - B[p] + C[q] - D[q]))→メスq-(1,0)→終点

であり、つがいにならなかった場合は、

始点-(1,0)→終点

のようにする。こうすれば始点と終点の間の辺はすべて同じになるので1つにまとめることができるようになる。

まとめると

さて、まとめるとフローは以下のようになる

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,A[p] - B[p] + C[q] - D[q]) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), 0) の辺を張る

min(P,Q)と書いているのはペアが作れるのは最大min(P,Q)組だけだからである。
これで最大費用流みたいな感じで流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+(最大費用)が答えになる。
ここまで理解できていればほぼほぼ答え。

最小費用流ですよ…

最大ではなく最小なので、コストを逆転させて負の数にすることで最大値を負の数にしたものを答えとして
出させるようにする。

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,-(A[p] - B[p] + C[q] - D[q])) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), 0) の辺を張る

最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)-(最小費用)が答えになる。
最小費用流はコストが正になる必要があるので、これもちょっとだめで、下駄をはかせる必要がある。
MAXを2*10⁹くらいに設定しておいて、つがいを作った場合とそうでない場合についてMAX分だけ
コストに下駄をはかせることにする。つまり…

始点から各オスpについて (1,0) の辺を張る
各オスpから各メスqについて (1,MAX-(A[p] - B[p] + C[q] - D[q])) の辺を張る
各メスqから終点について (1,0) の辺を張る
始点から終点について (min(P,Q), MAX) の辺を張る

こんな感じにする。
最小費用流をして流量min(P,Q)を流せば、(Bの総和)+(Dの総和)+MAX×min(P,Q)-(最小費用)が答えになる。
このように下駄を履かせた分だけ引けば全体を正のまま保ちつつ正答が得られる。

int P, Q;
string S[101];
ll A[101], B[101], C[101], D[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P >> Q;
    rep(p, 0, P) cin >> S[p];
    rep(p, 0, P) cin >> A[p] >> B[p];
    rep(q, 0, Q) cin >> C[q] >> D[q];

    atcoder::mcf_graph<int, ll> mcf(P + Q + 2);
    int st = P + Q;
    int gl = st + 1;
    int maxflow = min(P, Q);

    ll MAX = inf * 2;
    rep(p, 0, P) mcf.add_edge(st, p, 1, 0);
    rep(p, 0, P) rep(q, 0, Q) if (S[p][q] == '1') mcf.add_edge(p, P + q, 1, MAX-(A[p] - B[p] + C[q] - D[q]));
    rep(q, 0, Q) mcf.add_edge(P + q, gl, 1, 0);
    mcf.add_edge(st, gl, maxflow, MAX-0);

    int _; ll cost;
    tie(_, cost) = mcf.flow(st, gl, maxflow);

    ll ans = 0;
    rep(p, 0, P) ans += B[p];
    rep(q, 0, Q) ans += D[q];
    ans += MAX * maxflow - cost;
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

Happy Wedding! [第八回アルゴリズム実技検定 K]