【CF891C】Envy（最小生成树）

时间：2023-03-10 04:31:08
【CF891C】Envy（最小生成树）

【CF891C】Envy（最小生成树）

题面

Codeforces

洛谷

题解

考虑\(MST\)的构建过程，对于所有权值相同的边一起考虑。

显然最终他们连出来的结果是固定的。

把连边改为把联通块联通，这样子只需要检查询问中的权值相同的边连接这些联通块是否会成环。

并查集解决即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAX 500500

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int u,v,w,id;}e[MAX],p[MAX];

bool operator<(Line a,Line b){return a.w<b.w;}

bool cmp(Line a,Line b){return a.id<b.id;}

int n,m,Q,K,f[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

bool Work()

{

	K=read();for(int i=1;i<=K;++i)p[i]=e[read()];

	sort(&p[1],&p[K+1]);

	for(int i=1,j=1;i<=K;i=j=j+1)

	{

		while(j<K&&p[j+1].w==p[i].w)++j;

		for(int k=i;k<=j;++k)f[p[k].u]=p[k].u,f[p[k].v]=p[k].v;

		for(int k=i;k<=j;++k)

		{

			int u=getf(p[k].u),v=getf(p[k].v);

			if(u==v)return false;

			f[getf(u)]=getf(v);

		}

	}

	return true;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].id=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=j+1)

	{

		while(j<m&&e[j+1].w==e[i].w)++j;

		for(int k=i;k<=j;++k)e[k].u=getf(e[k].u),e[k].v=getf(e[k].v);

		for(int k=i;k<=j;++k)

		{

			int u=getf(e[k].u),v=getf(e[k].v);

			if(u==v)continue;f[getf(u)]=getf(v);

		}

	}

	sort(&e[1],&e[m+1],cmp);

	Q=read();while(Q--)puts(Work()?"YES":"NO");

	return 0;

}

相关文章