TopCoder SRM680(Div.1) Normal BearSpans

Posted on By 二价氢

题目大意

构造一个有\(n\)个结点,\(m\)条边的无向图,使得用Borůvka’s algorithm计算其最小生成树需要进行\(k\)轮主循环

解法

分析算法之后,我们可以知道,原来的题目就是要我们构造一棵有k层的树,每一个结点都至少有一个兄弟。而构造这样的一棵树很简单,像线段树那样递归即可。这样,每一个非叶子结点都对应了一棵菊花树,将第一个结点与剩下的结点连边即可。

最后将不在mst上的边随便加满\(m\)条即可。

###Code

class BearSpans {
public:
	vector<int> ans;
	set<pair<int, int> > se;
	int k, dep = 0;
	int cur;
	int n;
	void dfs(int lay, int l, int r) {
		if (r == n) {
			cerr << " " << l << "-" << r << endl; 
		} else {
			cerr << " " << l << "-" << r << ",";
		}
		if (lay == k || (r - l + 1) < 4) {
			dep = max(dep, lay);
			for (int i = l + 1; i <= r; i++) {
				ans.push_back(l);
				ans.push_back(i);
				se.erase(make_pair(l, i));
			}
			return;
		}
		int mid = (l + r) / 2;
		dfs(lay + 1, l, mid);
		dfs(lay + 1, mid + 1, r);
		ans.push_back(l);
		ans.push_back(mid + 1);
		se.erase(make_pair(l, mid + 1));
	}
	vector<int> findAnyGraph(int _n, int m, int _k) {
		k = _k;
		n = _n;
		if (int(log(n) / log(2) + 1e-6) < k) {ans.push_back(-1);return ans;}
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
				se.insert(make_pair(i, j));
		dfs(1, 1, n);
		if (k > dep || ans.size() > m * 2){ans.clear();ans.push_back(-1);return ans;}
		while (ans.size() < m * 2) {
			pair<int, int> pi = *se.begin();
			ans.push_back(pi.first);
		   	ans.push_back(pi.second);
			se.erase(*se.begin());
		}
		return ans;
	}
};

Level Upper 2016 - TopCoder 500 : 1 / 5