CF891C Envy【最小生成树】

题目链接

我们知道，根据Kruskal的贪心，对于最小生成树，每一种权值的边数是一样的，而且如果将\(\leq x\)的边做最小生成树，合法方案的联通性是一样的。所以我们可以对于所有边分开考虑。

对于一组询问，对于所有权值，权值为\(x\)的有\(k\)个，那么可以将\(<x\)的边全部加入，然后将这\(k\)个边加入，看看能不能全部加入进去。如果有一个成环了，那么肯定是不行的。

那么\(q\)组询问，可以离线下来，对于(边权,询问编号)二元组排序，然后对于同一边权的同一组询问，尝试加入，到了下一组询问就撤销，然后处理完之后又全部加入进去。用可撤销并查集就可以做了。

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 500003;
int n, m, k, q, mx, fa[N], siz[N];
bool ans[N];
struct Edge {
    int u, v, w;
    inline bool operator < (const Edge &o) const {return w < o.w;}
} e[N];
struct Query {
    int u, v, w, id;
    inline bool operator < (const Query &o) const {return id < o.id;}
};
vector<Query> vec[N];
inline int getfa(int x){
    return x == fa[x] ? x : getfa(fa[x]);
}
int stk[N], top;
inline bool comb(int x, int y){
    x = getfa(x); y = getfa(y);
    if(x != y){
        if(siz[x] > siz[y]) swap(x, y);
        siz[y] += siz[x]; fa[x] = y; stk[++ top] = x;
        return true;
    }
    return false;
}
int main(){
    scanf("%d%d", &n, &m);
    for(Rint i = 1;i <= m;i ++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), mx = max(mx, e[i].w);
    scanf("%d", &q);
    for(Rint i = 1;i <= q;i ++){
        scanf("%d", &k);
        while(k --){
            int now; scanf("%d", &now);
            vec[e[now].w].push_back((Query){e[now].u, e[now].v, e[now].w, i});
        }
    }
    for(Rint i = 1;i <= mx;i ++) if(!vec[i].empty())
        sort(vec[i].begin(), vec[i].end());
    sort(e + 1, e + m + 1);
    for(Rint i = 1;i <= n;i ++) siz[i] = 1, fa[i] = i;
    for(Rint i = 1;i <= q;i ++) ans[i] = true;
    for(Rint i = 1;i <= m;){
        int val = e[i].w; top = 0;
        for(Rint j = 0;j < vec[val].size();j ++){
            if(!ans[vec[val][j].id]) continue;
            if(j && vec[val][j].id != vec[val][j - 1].id){
                while(top){
                    siz[fa[stk[top]]] -= siz[stk[top]];
                    fa[stk[top]] = stk[top]; -- top;
                }
            }
            if(!comb(vec[val][j].u, vec[val][j].v)) ans[vec[val][j].id] = false;
        }
        while(e[i].w == val){
            comb(e[i].u, e[i].v); ++ i;
        }
    }
    for(Rint i = 1;i <= q;i ++) puts(ans[i] ? "YES" : "NO");
}

CF891C Envy【最小生成树】

原文：https://www.cnblogs.com/AThousandMoons/p/11609246.html