TopCoder SRM 680 Div1 Medium BearSpans

色んな解法がありそう。
https://community.topcoder.com/stat?c=problem_statement&pm=14128

問題

連結無向グラフの全域木を求めるBoruvkaのアルゴリズムを考える。
このアルゴリズムの概要は下記のとおりである。

• 集合Hは、グラフの連結成分を要素に持つ。初期状態では、集合Hはグラフの各点を含む。
• 以下をHの要素が1つになるまで繰り返す。
  • Hに含まれる各要素(連結成分)に対し、連結成分外の点とつながる最小コストの辺を求める。
  • 上記辺群により、H中の要素群をさらに連結させる。

「以下を～」の下りを1周行うことを１ラウンドとよぶ。

N頂点・M辺で構成される連結グラフを考える。
このM個の辺は、それぞれ長さが1,2,3...Mであるとする。
そのようなグラフ、上記アルゴリズムがKラウンドで終わるものを構築せよ。

解法

アルゴリズムを1ラウンド行うと、Hの要素数は最大でも半分になる。
よってKラウンド行うには最小2^K頂点必要であり、N＜2^Kなら解無しである。
以下N≧2^Kとする。

まずはKラウンドで全頂点が連結になるような(N-1)辺のつなぎ方を考える。
最初の1ラウンドで、連結成分が2^(K-1)個となるようにしよう。
例えばN=11,K=3なら、最初の1手で[1,2],[3,4],[5,6],[7,8,9,10,11]と連結されるよう1-2,3-4,5-6,7-8-9-10-11を辺で結ぶ。
あとは連結成分が2^(K-1)個なので、残り(K-1)ラウンドではラウンド毎に２要素を連結する辺を1個ずつ追加すればよい。

残り(M-(N-1))辺はあと適当に空いてる頂点群の間をつないでおけば良い。

int is[1010][1010];

class BearSpans {
	public:
	vector <int> findAnyGraph(int n, int m, int k) {
		int x,y,i;
		if(k>10 || n<1<<k) return {-1};
		
		ZERO(is);
		
		vector<int> R;
		vector<pair<int,int>> V;
		FOR(i,1<<(k-1)) V.push_back({i*2+1,i*2+2});
		V.back().second=n;
		
		FORR(r,V) for(x=r.first;x<r.second;x++) R.push_back(x),R.push_back(x+1), is[x][x+1]++, m--;
		
		while(V.size()>1) {
			vector<pair<int,int>> V2;
			FOR(i,V.size()/2) {
				R.push_back(V[i*2].first);
				R.push_back(V[i*2+1].first);
				m--;
				is[V[i*2].first][V[i*2+1].first]++;
				V2.push_back({V[i*2].first,V[i*2+1].second});
			}
			swap(V,V2);
		}
		FOR(y,n) FOR(x,y) if(is[x+1][y+1]==0 && m) m--, R.push_back(x+1),R.push_back(y+1);
		return R;
	}
}

まとめ

SRMも最近Constructive出るようになってきたな…。