AtCoder ARC121 B - RGB Matching 後半パートの最小費用流による解法 MinCostFlow

最小費用流を初めて使いました．

題意(省略)

こう考えた

まず、大枠の考え方は解説と同じです．$2N$の犬の各色がすべて偶数の場合、不満は起きないので答えは$0$です．
犬の色を変えても一般性を失わないので、Rを偶数匹、B,Gを奇数匹とします．この時、最小の値となるには、以下の最小です．

• パターンA: BとGから不満が最小のペアを取る
• パターンB: RとB、RとGの不満が合計が最小となるのペアを１つずつとる．この時、BとGがとるRは同じ犬ではいけない

まず、パターンAを考えるとこれは

• 一方をソートして、もう一方の値を二分探索し、挿入できる配列の左右の要素とabsを取り、小さい方の値、　の最小値

です．例えば、$[2,4,7,8]$のとき、$5$を考えると、二分探索で4と７の間に挿入できますが、差は1と2なので１を考えます．この場合では、5は4とペアを組み、不満１が最小．と言えます．このように、もう一方の配列の値を$O(logN)$で検索することで、全体としては$O(MlogN)$でパターンAの値を求められます．

パターンBについて、結論としては、パターンAの応用でも解けます．RとG, RとBに対して、パターンAと同じ処理を行いそれぞれの結果をリストに記録し、この際、選ばれたRのインデックスを記録します．両方の結果、最小の値となるインデックスが同じであれば、片方を次点の値とすることとし、どちらの値を取るかを計算すれば良いです．

パターンBの最小費用流考察

今回のパターンBでは上記の考え方で良いですが、最小費用流を使って考えてみます．突然ですが、以下のようにグラフを作ります．以下「流せるフロー/フローごとのコスト」で示します．
この問題では過剰ですが、例えばRとGは2本、RとBは3本選んだときの最小値は？や、B,Gだけでなくもっと種類がある時など、グラフを作ればだけなので楽です．

• 始点Sは各R(even)に対して1/0の辺を張ります．つまり、各Rは一度しか選べません
• 各RはG(odd1)に対してパターンAと同じ処理を行い、「1/(Gのどれかと組み合わせる最小コスト)」を張ります．この時、Gのノードは１つずつ作っても良いですが、Gとして１つにまとめてしまって良いです．(つまり、$|G|$このノードは不要です)
• 同じようにB(odd2)も辺を張ります．
• G, Bでまとめたノードから1/0をTに張ります
• この上でSからTに流量2を流そうとして、2流れたときのコストが答えです

このグラフはG,Bの各要素をノードとして生成しても解けます．その場合、G,BとTの間にはノードを作ってやり、1/0でに辺を貼って、G,Bが共に1までしか選べないようにする必要があります．この場合は以下のようにします．

実装

#include <bits/stdc++.h>
#include <atcoder/all>
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) FOR(i,0,n)

#define FASTIO() cin.tie(0); ios::sync_with_stdio(false)

using namespace std;
using namespace atcoder;
const int numNode = 2*100000;
const int numColor = 4 * 100000;
const int numGraph = numNode + numColor + 100;
const int snode = numGraph - 3;
const int tnode = numGraph - 2;
using ll = long long;

// lからxに一番近い数字を探し距離(絶対値)を返す
// l, xはTを要求する
template <typename T>
T mindiffsearch(vector<T> &l, T x){
    auto sz = l.size();
    auto p = lower_bound(l.begin(), l.end(), x);
    auto indl = distance(l.begin(), p);
    if(indl == 0) return abs(x - l.at(0));
    if(indl == sz) return abs(x - l.at(sz-1));
    return min(abs(x - l.at(indl)), abs(x - l.at(indl - 1)));
}

int main(int argc, char *argv[]) {
    FASTIO();
    int n; cin >> n;
    vector<int> cnt(3);
    vector<vector<ll>> dat(3);
    REP(i, n*2){
        ll a; string b;
        cin >> a >> b;
        if(b.at(0) == 'R') {dat.at(0).emplace_back(a);      cnt.at(0)++; }
        else if(b.at(0) == 'G') {dat.at(1).emplace_back(a); cnt.at(1)++; }
        else if(b.at(0) == 'B') {dat.at(2).emplace_back(a); cnt.at(2)++; }
        else { assert(false); }
    }

    // 全部偶数のときは0が答え
    if( (cnt.at(0)%2 + cnt.at(1)%2 + cnt.at(2)%2) == 0){
        cout << 0 << "\n";
        return 0;
    }

    // 偶数を[0]にもっていく
    if(cnt.at(0)%2 == 0) {}
    else if(cnt.at(1)%2 == 0) {swap(cnt.at(0), cnt.at(1)); swap(dat.at(0), dat.at(1)); }
    else if(cnt.at(2)%2 == 0) {swap(cnt.at(0), cnt.at(2)); swap(dat.at(0), dat.at(2)); }
    else { assert(false); }

    REP(i, 3) sort(ALL(dat.at(i)));

    // 奇数1と奇数２から最小の差の値だけを得る
    ll res1 = 1e18;
    REP(i, cnt.at(1)){
        auto x = dat.at(1).at(i);
        res1 = min(res1, mindiffsearch(dat.at(2), x));
    }

    // 偶数と奇数1, 偶数と奇数2 を重複なく取る
    ll res2 = 1e18;
    {
        if (cnt.at(0) > 0) {
            int nodeS = 2 * n, nodeT = 2 * n + 1;
            int node1 = 2 * n + 2, node2 = 2 * n + 3;
            mcf_graph<int, long long> mcf(2 * n + 4);
            mcf.add_edge(node1, nodeT, 1, 0);
            mcf.add_edge(node2, nodeT, 1, 0);
            REP(i, cnt.at(0)) {
                mcf.add_edge(nodeS, i, 1, 0);
                mcf.add_edge(i, node1, 1, mindiffsearch(dat.at(1), dat.at(0).at(i)));
                mcf.add_edge(i, node2, 1, mindiffsearch(dat.at(2), dat.at(0).at(i)));
            }
            auto result = mcf.flow(nodeS, nodeT, 2);
            assert(result.first == 2);
            res2 = result.second;
            // フローを流した後の結果．これでflowをみると使った辺が復元できる
            //for (auto e: mcf.edges()) {
            //    cout << "s,t=" << e.from << "," << e.to << ", cap/cost"", " << e.cap << "," << e.cost << " flow:" << e.flow << "\n";
            //}
            //cout << "mcf:" << result.first << "-" << result.second << "\n";
        }
    }

    cout << min(res1, res2) << "\n";

}