CF891C Envy
原题链接：CF891C Envy
Tag：MST
题目描述
对于一个连通的无向带权图 \(G\)，MST（最小生成树）是 \(G\) 的一个子图， 包含 \(G\) 的所有顶点，是一棵树，并且其所有边的权值之和尽可能小。
给定一个图 \(G\)。如果你在该图上运行最小生成树算法， 只会得到一棵最小生成树，这就让其它边“嫉妒”了。 你会得到若干个询问，每个询问包含 \(G\) 的一个边集合， 你需要判断是否存在一棵包含这些边的最小生成树。
数据说明：
\(2 \leq n,m \leq 5 \cdot 10^5\)，\(n-1 \leq m\)
\(u_i \neq v_i\)，\(1 \leq w_i \leq 5 \cdot 10^5\)
\(1 \leq q \leq 5 \cdot 10^5\)，\(1 \leq k_i \leq n-1\)
保证所有询问的 \(k_i\) 之和不超过 \(5 \cdot 10^5\)。
分析
首先回顾一下 \(\text{Kruskal}\) 的过程：
- 按照权值从小到大扫描边
- 如果一个边的两个点处在不同的连通块中就选，反之跳过。
我们可以从「按权值分层」的角度来重新审视 \(\text{Kruskal}\)：
当我们处理到某个权值 \(w\) 时，所有权值 \(< w\) 的边一定已经产生了若干连通块，而对于边权 \(=w\) 的边， 我们就要从这些边里挑选一些出来，只要这些边不成环，无论怎么选都不会影响到最优性。
也就是说，当我们考虑到权值 \(w\) 时，整个图已经被边权 \(<w\) 的边缩成了若干块， 而我们在这些块之间挑选权值为 \(w\) 的边时，只要这些边没有形成环，就能出现在某个 \(\text{MST}\) 中。
思考出以上内容还是比较平凡的，之后我们发现 \(n,m,q\) 最大都有 \(5e5\) 的值，而且 \(\sum k\) 最大也有 \(5e5\)， 所以如果我们要对每一个询问都跑一次 \(\text{Kruskal}\) 一定是不对的。
我们可以先把原图中的边权排序，之后把询问记录成 \((w,qid,eid)\) 的形式， 其中 \(w\) 代表边的权值，之后以 \(w\) 作为第一关键字，\(qid\) 作为第二关键字进行排序。
维护一个全局的 \(\text{DSU}\)，用它来记录已经加入了所有边权 \(<w\) 的状态。
之后我们从小到大考虑所有出现的 \(w\)，首先对于 \(qid\) 相同的这些边， 我们要判断其是否出现自环，或者这些边连到一起之后是否会出现环，这一步可以开一个临时的 \(\text{DSU}\) 实现。 一旦出现了环的状况，答案自然是 \(\text{NO}\)。
之后把所有边权 \(=w\) 的边，使用全局的 \(\text{DSU Union}\) 到一起， 这样一来复杂度为 \(O((m+\sum k) \log \sum k)\)。
代码实现
struct DSU {
public:
vector<int> bcj;
vector<int> siz;
void Init(int n) {
bcj.resize(n + 1);
siz.resize(n + 1);
for (int i = 1; i <= n; ++i) {
bcj[i] = i;
siz[i] = 1;
}
}
int Find(int x) {
if (bcj[x] == x) return x;
return bcj[x] = Find(bcj[x]);
}
// 按秩合并
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
bcj[x] = y;
siz[y] += siz[x];
}
};
void IHaveNoLimitation() {
int n, m;
cin >> n >> m;
struct edge {
int u, v, w;
};
vector<edge> E(m + 1);
vector<int> W;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
E[i] = {u, v, w};
W.push_back(w);
}
int q;
cin >> q;
vector<int> ans(q, 1);
struct query {
int w, qid, eid;
};
vector<query> querys;
for (int i = 0; i < q; i++) {
int k;
cin >> k;
while (k--) {
int id;
cin >> id;
querys.push_back({E[id].w, i, id});
W.push_back(E[id].w);
}
}
std::sort(W.begin(), W.end());
W.erase(std::unique(W.begin(), W.end()), W.end());
vector<int> Eidx(m);
std::iota(Eidx.begin(), Eidx.end(), 1);
std::sort(Eidx.begin(), Eidx.end(), [&](int a, int b) {
return E[a].w < E[b].w;
});
std::sort(querys.begin(), querys.end(), [&](query a, query b) {
if (a.w != b.w) return a.w < b.w;
return a.qid < b.qid;
});
DSU dsu;
dsu.Init(n);
int p1 = 0, p2 = 0;
for (auto &w: W) {
int rL = p2;
while (p2 < querys.size() && querys[p2].w == w) p2++;
for (int i = rL; i < p2;) {
int qid = querys[i].qid;
int j = i;
while (j < p2 && querys[j].qid == qid) j++;
if (ans[qid]) {
vector<int> tmp;
vector<PII> pairs;
bool f = 0;
for (int t = i; t < j; t++) {
int id = querys[t].eid;
int a = dsu.Find(E[id].u);
int b = dsu.Find(E[id].v);
if (a == b) {
f = 1;
break;
}
pairs.push_back({a, b});
tmp.push_back(a),tmp.push_back(b);
}
if (!f) {
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
vector<int> p(tmp.size()), sz(tmp.size(), 1);
std::iota(p.begin(), p.end(), 0);
auto Find = [&](int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
};
auto Union = [&](int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return false;
if (sz[x] < sz[y]) swap(x, y);
p[y] = x;
sz[x] += sz[y];
return true;
};
for (auto &[a, b]: pairs) {
int ia = lower_bound(tmp.begin(), tmp.end(), a) - tmp.begin();
int ib = lower_bound(tmp.begin(), tmp.end(), b) - tmp.begin();
if (!Union(ia, ib)) {
f = 1;
break;
}
}
}
if (f) ans[qid] = 0;
}
i = j;
}
while (p1 < Eidx.size() && E[Eidx[p1]].w == w) {
int id = Eidx[p1];
dsu.Union(E[id].u, E[id].v);
p1++;
}
}
for (auto &x: ans) {
if (x) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
日志
本页面创建于 2026/3/1 16:38