kmjp's blog

競技プログラミング参加記です

Grakn Forces 2020 : E. Avoid Rainbow Cycles

割と出来の良かった回。
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;
}

まとめ

気付いてしまえば実装は軽い。