【CF891C】Envy [最小生成树]

CF891C Envy

CF891C luogu

==是看的yyb的

1. 对于任意权值的边，所有最小生成树中这个权值的边的数量是一定的
2. 对于任意正确加边方案，加完小于某权值的所有边后图的连通性是一样的

将所有权值相同的边一起考虑 由2可得它们连出来的结果是固定的

将连边改为脸连通块

预处理时将每个小于\(w_i\)的边先加入 再加入边权为\(w_i\)的边 若形成环 则这组询问失败

在每次寻问候要将这次询问所构成的修改还原==

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int>pii;
const int N=5e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m,s,tt,f[N];
template<class t>void rd(t &x){
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

struct edge{
    int u,v,w,id;
    bool operator<(const edge&X)const{return w<X.w;}
}e[N],q[N];
bool cmp(edge X,edge Y){return X.id<Y.id;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

bool kruskal(){
    int K;rd(K);
    for(int i=1,x;i<=K;++i) rd(x),q[i]=e[x];
    sort(q+1,q+K+1);
    for(int i=1,j=1;i<=K;i=++j){
        while(j<K&&q[j+1].w==q[j].w) ++j;
        for(int k=i;k<=j;++k) f[q[k].u]=q[k].u,f[q[k].v]=q[k].v;
        for(int k=i;k<=j;++k){
            if(find(q[k].u)==find(q[k].v)) return 0;
            f[f[q[k].u]]=f[q[k].v];
        }
    }
    return 1;
}


int main(){
    freopen("in.txt","r",stdin);
    rd(n),rd(m);
    for(int i=1,u,v,w;i<=m;++i) rd(u),rd(v),rd(w),e[i]=(edge){u,v,w,i};
    for(int i=1;i<=n;++i) f[i]=i;
    sort(e+1,e+m+1);
    for(int i=1,j=1;i<=m;i=++j){
        while(j<m&&e[j+1].w==e[j].w) ++j;
        for(int k=i;k<=j;++k) e[k].u=find(e[k].u),e[k].v=find(e[k].v);
        for(int k=i;k<=j;++k)
        if(find(e[k].u)!=find(e[k].v)) f[f[e[k].u]]=f[e[k].v];
    }
    sort(e+1,e+m+1,cmp);
    rd(m);while(m--) puts(kruskal()?"YES":"NO");
    return 0;
}