むずかしい
問題概要
長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。
さらに、 系列の数列が与えられる。
- 番目の数列の項数は で与えられる
- 数列の各項 は 以上 以下の値である
今、以下の操作を行う。
- 、 を満たす を選ぶ
- これに要するコストは で与えられる
- 番目の数列に値 の項が存在するならば除去する
これらの操作後に次のようなグラフを作る。
- 頂点集合は である
- 各 に対して、値 がともに 番目の数列に含まれるとき、二頂点 を色 の辺でむすぶ
このグラフが「カラフルなサイクル」を持たないようにしたい。それが可能となる最小コストを求めよ。
制約
- の総和 ( とする) が 以下
考えたこと
問題設定が複雑だけど、とりあえず「頂点」と「色」という 2 つのステークホルダーがいるので二部グラフで整理するとよさそう。また、
「頂点 が色 の辺でクリークをなす」
という状況に対して、色 に対応するスーパーノードを用意して、それと頂点 とを結んだグラフを考えるのは自然ではある。このとき、数列 から値 を削除する操作は、この二部グラフの辺 を削除することに対応している。
この二部グラフがサイクル (同じ頂点は二度通らない) をもつとき、元のグラフはカラフルなサイクルをもつ。逆に元のグラフがカラフルなサイクルをもつとき、この二部グラフはカラフルなサイクルをもつ。
よって問題は、最小コストの辺を取り除いて、二部グラフを木にする問題だといえる。よって、二部グラフの最大全域木のサイズを求めれば OK。計算量は 。
コード
#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; }