题解 [CF891C] Envy

题面

解析

首先根据Kruskal算法,

我们可以知道,

在加入权值为(w)的边时,

权值小于(w)的边都已经加进树里了(除了连成环的).

所以,我们可以保存一下每条边的端点在加入生成树之前的连通块,

把询问的边按边权排序,

对于每组边权相同端的边,

把它恢复到加入这种权值的边的连通情况,

在判断能否形成环就行了.

(可能还有很多一些细节要注意)

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;

inline int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return f*sum;
}

const int N=500001;
struct edge{int fx,fy,x,y,w,id;}e[N<<1];
int n,m,Q;
int fa[N];
vector <int> s;

bool cmp(edge a,edge b){return a.w<b.w;}
bool cmp2(edge a,edge b){return a.id<b.id;}
bool cmp3(int a,int b){return e[a].w<e[b].w;}

inline int find_fa(int x){return x==fa[x]? x:fa[x]=find_fa(fa[x]);}

int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].w=read();
	for(int i=1;i<=m;i++) e[i].id=i;
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+m+1,cmp);e[0].w=-1;
	for(int i=1;i<=m;){
		int j=i;
		do{e[j].fx=find_fa(e[j].x);e[j].fy=find_fa(e[j].y);j++;}while(e[i].w==e[j].w&&j<=m);
		while(i<j){
			while(find_fa(e[i].x)==find_fa(e[i].y)&&i<j) i++;
			if(i<j) fa[find_fa(e[i].x)]=find_fa(e[i].y);
		}
	}
	sort(e+1,e+m+1,cmp2);
	Q=read();
	for(int i=1;i<=n;i++) fa[i]=i;
	while(Q--){
		int ok=1,ss=read();
		for(int i=1;i<=ss;i++){int x=read();s.push_back(x);}
		sort(s.begin(),s.end(),cmp3);
		int sz=s.size();
		for(int i=0;i<sz&&ok;){
			if(e[s[i]].fx==e[s[i]].fy){ok=0;break;}
			fa[find_fa(e[s[i]].fx)]=find_fa(e[s[i]].fy);
			int j=i+1;
			while(j<sz&&e[s[i]].w==e[s[j]].w){
				if(find_fa(e[s[j]].fx)==find_fa(e[s[j]].fy)){ok=0;break;}
				fa[find_fa(e[s[j]].fx)]=find_fa(e[s[j]].fy);j++;
			}
			while(i<j) fa[e[s[i]].fx]=e[s[i]].fx,fa[e[s[i]].fy]=e[s[i]].fy,i++;			
		}
		puts(ok? "YES":"NO");s.clear();
	}
	return 0;
}