CF891C Envy

传送门

Luogu

Solution

考虑最小生成树的性质，即相同边权构成的连通性相同，所以我们只需要把边权排序然后将相同的连起来判断是否冲突即可。

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=500010;
struct node
{
    int u,v,w,uu,vv,id;
    bool operator<(const node&b)const
        {
            return w<b.w;
        }
}e[N],a[N];
int f[N],n,m,q,c[N],id[N];
int find(int x)
{
    if(f[x]!=x)f[x]=find(f[x]);
    return f[x];
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    n=gi();m=gi();
    for(int i=1;i<=m;i++)
    {
        e[i].u=gi(),e[i].v=gi(),e[i].w=gi();
        e[i].id=i;

    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++)
        id[e[i].id]=i;
    for(int i=1;i<=n;i++)f[i]=i;
    int last=1;
    for(int i=1;i<=m;i++)
    {
        if(e[i].w!=e[i-1].w)
        {
            for(int j=last;j<i;j++)
            {
                int u=find(e[j].u),v=find(e[j].v);
                if(u!=v)f[v]=u;
            }
            last=i;
        }
        e[i].uu=find(e[i].u);
        e[i].vv=find(e[i].v);
    }
    for(int j=last;j<=m;j++)
    {
        int u=find(e[j].u),v=find(e[j].v);
        if(u!=v)f[v]=u;
    }
//  for(int i=1;i<=m;i++)
//      printf("%d %d %d %d %d\n",e[i].u,e[i].v,e[i].w,e[i].uu,e[i].vv);
    q=gi();
    while(q--)
    {
        int k=gi(),sta=0;
        for(int i=1;i<=k;i++)
            c[i]=gi();
        for(int i=1;i<=k;i++)
        {
            a[++sta]=e[id[c[i]]];
            f[a[sta].uu]=a[sta].uu;
            f[a[sta].vv]=a[sta].vv;
        }
        sort(a+1,a+sta+1);int flag=0;
        for(int i=1;i<=sta;i++)
        {
            int u=a[i].uu,v=a[i].vv;
            if(find(u)==find(v))
            {
                flag=1;break;
            }
//          if(!q)printf("%d %d %d %d\n",u,v,find(u),find(v));
            f[find(u)]=find(v);
        }
        if(flag)puts("NO");
        else puts("YES");
    }
    return 0;
}