割と出来の良かった回。
https://codeforces.com/contest/1408/problem/E
問題
M個の整数集合A[i]が与えられる。
各集合の中身は、1~Nの範囲の整数である。
数列a,bが与えられており、A[i]から値jを取り除くには、a[i]+b[j]のコストがかかる。
ここで、N頂点のグラフを考える。
各整数集合Aにおいて、同じ集合に含まれる整数に対応する頂点間を、色iの辺でつなぐ。
ここで、閉路が虹色であるとは、全辺が異なる色である閉路を意味する。
このグラフで虹色の閉路ができないようA[i]から値を取り除くとき、その総コストを最小化せよ。
解法
M+N頂点の2部グラフを考える。
A[i]に値jがあるとき、左側の点iから右側の点jに辺を張ろう。
このグラフに閉路がなければ虹色の閉路はできない。
そこで、コストの高い順に辺を追加していき、閉路ができないように追加しない辺を選んでいこう。
template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<202020> uf; int M,N; int A[101010],B[101010]; vector<pair<int,pair<int,int>>> P; vector<pair<int,int>> V[101010]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&M,&N); FOR(i,M) { scanf("%d",&A[i]); } FOR(i,N) scanf("%d",&B[i]); FOR(i,M) { scanf("%d",&x); while(x--) { scanf("%d",&y); P.push_back({A[i]+B[y-1],{i,y-1}}); } sort(ALL(V[i])); reverse(ALL(V[i])); } sort(ALL(P)); reverse(ALL(P)); ll ret=0; FORR(p,P) { x=p.second.first; y=p.second.second+100000; if(uf[x]==uf[y]) { ret+=p.first; } else { uf(x,y); } } cout<<ret<<endl; }
まとめ
気付いてしまえば実装は軽い。