HackerRank HourRank 22 : B. Super Mancunian

Tシャツゲットできてよかったです。
https://www.hackerrank.com/contests/hourrank-22/challenges/super-mancunian

問題

各辺コスト付の無向グラフから最小全域木を作りたい。
その際、1本だけグラフのコストを0にできるとき、最小コストとコストを0にする辺の候補の数を答えよ。

解法

まずはUnion-Findを使い普通に最小全域木を作ってみる。
最小全域木を作るのに必要な最大コストをCとする。

1本の辺のコストを0にして総コストを最小化したいので、コストを0にする辺はC以上のものである。
逆にC未満の辺は手を加えない。

よって再度最小全域木の処理を実行し、C未満の辺の分の処理を行おう。
この時点で非連結な成分を結ぶ残りの辺は、コスト0にすることで利用価値がでるのでそのような辺を数え上げればよい。

int N,M;
ll sum;
map<int,int> mp;

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<200000> uf,uf2;
int NN;
map<int,vector<pair<int,int>>> E;

void solve() {
	int i,j,k,l,x,y; string s;
	
	cin>>N>>M;
	if(N==1) _P("0 0\n");
	FOR(i,M) {
		cin>>x>>y>>j;
		E[j].push_back({x-1,y-1});
	}
	NN=N;
	
	int mi;
	FORR(e,E) {
		FORR(rr,e.second) {
			if(uf[rr.first]!=uf[rr.second]) {
				uf(rr.first,rr.second);
				sum+=e.first;
				NN--;
			}
		}
		if(NN==1) {
			sum-=e.first;
			mi=e.first;
			break;
		}
	}
	
	int cand=0;
	FORR(e,E) {
		if(e.first<mi) {
			FORR(rr,e.second) uf2(rr.first,rr.second);
		}
		else {
			FORR(rr,e.second) if(uf2[rr.first] != uf2[rr.second]) cand++;
		}
	}
	
	cout<<sum<<" "<<cand<<endl;
}

まとめ

一ひねりが必要な問題でした。