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

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

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい

問題へのリンク

問題概要

長さ  M の数列  a_{1}, \dots, a_{M} と、長さ  N の数列  b_{1}, b_{2}, \dots, b_{N} が与えられる。これらはある操作のコストを決めるためのパラメータである。

さらに、 M 系列の数列が与えられる。

  •  i 番目の数列の項数は  s_{i} で与えられる
  • 数列の各項  A_{1}, \dots, A_{s_{i}} 1 以上  N 以下の値である

今、以下の操作を行う。

  •  1 \le i \le M 1 \le j \le N を満たす  (i, j) を選ぶ
  • これに要するコストは  a_{i} + b_{j} で与えられる
  •  i 番目の数列に値  j の項が存在するならば除去する

これらの操作後に次のようなグラフを作る。

  • 頂点集合は  1, 2, \dots, N である
  •  i = 1, 2, \dots, M に対して、値  u, v がともに  i 番目の数列に含まれるとき、二頂点  u, v を色  i の辺でむすぶ

このグラフが「カラフルなサイクル」を持たないようにしたい。それが可能となる最小コストを求めよ。

制約

  •  M, N \le 10^{5}
  •  s_{i} の総和 ( S とする) が  2 \times 10^{5} 以下

考えたこと

問題設定が複雑だけど、とりあえず「頂点」と「色」という 2 つのステークホルダーがいるので二部グラフで整理するとよさそう。また、

「頂点  A_{1}, \dots, A_{s_{i}} が色  i の辺でクリークをなす」

という状況に対して、色  i に対応するスーパーノードを用意して、それと頂点  A_{1}, \dots, A_{s_{i}} とを結んだグラフを考えるのは自然ではある。このとき、数列  i から値  j を削除する操作は、この二部グラフの辺  (i, j) を削除することに対応している。

この二部グラフがサイクル (同じ頂点は二度通らない) をもつとき、元のグラフはカラフルなサイクルをもつ。逆に元のグラフがカラフルなサイクルをもつとき、この二部グラフはカラフルなサイクルをもつ。

よって問題は、最小コストの辺を取り除いて、二部グラフを木にする問題だといえる。よって、二部グラフの最大全域木のサイズを求めれば OK。計算量は  O(N + M + S \log S)

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    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);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

using pint = pair<int,int>;
using Edge = pair<long long, pint>;
int main() {
    int M, N;
    cin >> M >> N;
    vector<long long> a(M), b(N);
    for (int i = 0; i < M; ++i) cin >> a[i];
    for (int j = 0; j < N; ++j) cin >> b[j];
    
    UnionFind uf(M + N);
    vector<Edge> edges;
    long long sum = 0;
    for (int i = 0; i < M; ++i) {
        int s; cin >> s;
        for (int j = 0; j < s; ++j) {
            int v; cin >> v; --v;
            edges.push_back(Edge(a[i] + b[v], pint(i, v + M)));
            sum += a[i] + b[v];
        }
    }
    sort(edges.begin(), edges.end(), greater<Edge>());
    long long res = 0;
    for (auto e : edges) {
        int u = e.second.first, v = e.second.second;
        if (uf.issame(u, v)) continue;
        res += e.first;
        uf.merge(u, v);
    }
    cout << sum - res << endl;
}