kmjp's blog

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

World CodeSprint 8 : C. Roads and Libraries

無理やりマラソン問題を乱数解でゴリ押してprize圏内に入った。
https://www.hackerrank.com/contests/world-codesprint-8/challenges/torque-and-development

問題

町を頂点、道路を辺に見立てた無向グラフが与えられる。
ただし道路は壊れており利用できない。

一部の町に病院を作り、また道路を修理し、各町が最低1個の病院に到達可能となるようにしたい。
病院設立および道路修理のコストが与えられたとき、条件を満たす最小コストを求めよ。

解法

各連結成分に対し処理する。
連結成分内に病院を1個立てて残りは道路を修理するか、全町に病院を建てるか安い方をとればよい。

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<110000> uf;

int Q,N,M;
ll CR,CL;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		uf.reinit();
		cin>>N>>M>>CL>>CR;
		FOR(i,M) {
			cin>>x>>y;
			uf(x-1,y-1);
		}
		ll ret=0;
		FOR(i,N) if(uf[i]==i) ret += CL+min(CL,CR)*(uf.count(i)-1);
		cout<<ret<<endl;
		
	}
}

まとめ

これはだいぶ簡単。