题解 [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;

}

巴特西

题解 [CF891C] Envy

解析

最新文章

热门文章