無理やりマラソン問題を乱数解でゴリ押して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; } }
まとめ
これはだいぶ簡単。