题目大意
构造一个有\(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