マトロイドだ！！！！！！！

問題概要

$H \times W$ のボード上の $N$ 個のコマがあってそれぞれ重みがつけられている。同じマスに複数のコマが置かれていることもある。

今、各行から 1 個以下のコマを取り去る。次に各列から 1 個以下のコマを取り去る。

最終的に取り去ったコマの重みの総和の最大値を求めよ。

制約

$1 \le H, W, N \le 10^{5}$

考えたこと

すごく面白そう！！！！！
一見してフローを疑いたくなる問題設定なのだけど、今回はたとえば各行から選ぶフェーズにおいて

(1, 9)
(2, 9)
(3, 9)
(4, 9)
...

みたいに列が共通していても構わない。なのであまりフローっぽくない (フローは各行各列ともに 1 個ずつ取るような問題設定で活躍したりする)。それに制約が大きい！！！！！

こういうの Greedy しかなさそうだよね (最悪だけどこういうメタ読みは重要な気がする)。

あともう一つ思うことは、「各行を選ぶ」 -> 「各列を選ぶ」という順序で選んでいるけど、この順序にさしたる意味はなさそう。それよりも選ばれるコマ集合として最終的にどのようなものがありうるかをわかりやすく特徴づけることが重要そう。

二部グラフにする

二次元グリッド問題の一つの定番として、二部グラフで考えるというのがある。その典型的な問題としては、以下のものがある。

drken1215.hatenablog.com

行を左側頂点に対応させ、列を右側頂点に対応させ、各コマを対応する左頂点・右頂点をむすぶ辺に対応させた二部グラフを考える。このグラフ上で考えると、問題は

各頂点につき、それに接続している辺を高々一本ずつ選ぶ
その選ばれた辺集合の重みの最大値を求めよ

ということになる。そしてこの「各頂点につきそれに接続している辺を高々一本ずつ選んだもの」は実は割とよくみるマトロイドなのだ。

マトロイド上の Greedy へ

「各頂点につきそれに接続している辺が高々一本ずつ」をとってきてできる部分グラフをさらに詳しく述べると、各連結成分が

なもりグラフ (サイクルを一つだけもつ連結なグラフ)
ツリー

のいずれかになっていることと同値であることがわかる。最小全域ツリー問題が貪欲法に基づいた Kruskal 法で解けるのと同様、この「重みが最大の、各連結成分がなもりかツリーになっている部分グラフを求める問題」も同様の貪欲法によって解くことができる。

すなわち辺を重みが大きい順にソートして、辺を追加していき、上の条件を満たさないような辺は捨てるアルゴリズム。実装上は Union-Find を用いつつ、各連結成分に対して、なもりかツリーかの情報を持たせると良さそう。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct UnionFind {
    vector<int> par;
    vector<bool> is_namori;
    
    UnionFind(int n) : par(n, -1), is_namori(n, 0) {}
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    // e = (x, y) を結んで良いかどうかも含めて判定
    bool merge(int x, int y) {
        x = root(x); y = root(y);

        // x と y が同じ連結成分
        if (x == y)  {
            if (is_namori[x]) return false;
            is_namori[x] = true;
            return true;
        }

        // x も y もなもりはダメ
        if (is_namori[x] && is_namori[y]) return false;
        
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        if (is_namori[x] || is_namori[y]) is_namori[x] = true;   
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

using pint = pair<int,int>;
using Edge = pair<long long, pint>;

int main() {
    int N, H, W; cin >> N >> H >> W;
    vector<Edge> edges;
    for (int i = 0; i < N; ++i) {
        int r, c, a; cin >> r >> c >> a; --r, --c;
        c += H;
        edges.push_back(Edge(a, pint(r, c)));
    }
    sort(edges.begin(), edges.end(), greater<Edge>());

    UnionFind uf(H + W);
    long long res = 0;
    for (auto e : edges) {
        int u = e.second.first;
        int v = e.second.second;
        long long w = e.first;

        if (uf.merge(u, v)) res += w;
    }   
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

第一回日本最強プログラマー学生選手権-予選- E - Card Collector (4D, 橙色, 800 点)

問題概要

制約

考えたこと

二部グラフにする

マトロイド上の Greedy へ