2024 sheep

类似最小生成树，对边排序依次加上，但是数据大，要进行离线处理，存起来，将比他小的边加上，判断连通用并查集（路径压缩，按秩合并）。

唐完的我在赛时没写按秩，而且while没写终止条件（唐老鸭）。

先按秩后合并，测评机有点玄学但确实要这样。

初版：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int ans[N];
int n,m,q;
int siz[N];
struct ss{
	int u,v,w;
}e[N];

struct sa{
	int s,t,c,id;
}a[N];

bool cmp(ss g,ss h){
	return g.w<h.w;
}

bool cmp2(sa g,sa h){
	return g.c<h.c;
}

int fa[N];
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}

int main(){
	freopen("sheep.in","r",stdin);
	freopen("sheep.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=q;i++){
		cin>>a[i].s>>a[i].t>>a[i].c;
		a[i].id=i;
	}
	sort(a+1,a+q+1,cmp2);
	int j=1;
	int x,y;
	for(int i=1;i<=m;i++){
		while(e[i].w>a[j].c&&j<=q){
			if(find(a[j].s)==find(a[j].t)){
				ans[a[j].id]=1;
			}
			++j;
		}
		x=find(e[i].u);
		y=find(e[i].v);
		if(x==y){
			continue;
		}
		if(siz[x]>siz[y]){
			swap(x,y);
		}
		siz[y]+=siz[x];
		fa[x]=y;
	}
	while(j<=q){
		ans[a[j].id]=(find(a[j].s)==find(a[j].t));
		j++;
	} 
	for(int i=1;i<=m;i++){
		if(ans[i]){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
	}
	return 0;
}

抄版：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool ans[N];
int n,m,q;
int siz[N];
struct ss{
	int u,v,w;
	int id;
}e[N],a[N];

bool cmp(ss g,ss h){
	return g.w<h.w;
}

int fa[N];
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}

void merge(int u,int v){
	u=find(u);
	v=find(v);
	if(u==v){ 
		return;
	}
	if(siz[u]>siz[v]){
		swap(u,v);
	}
	fa[u]=v;
	siz[v]+=siz[u];
	return;
}

int main(){
	freopen("sheep.in","r",stdin);
	freopen("sheep.out","w",stdout);
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>q;
	
	for(int i=1;i<=n;i++){
		fa[i]=i;
		siz[i]=1;
	}
		
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}

	for(int i=1;i<=q;i++){
		cin>>a[i].u>>a[i].v>>a[i].w;
		a[i].id=i;
	}
	
	sort(e+1,e+m+1,cmp);
	sort(a+1,a+q+1,cmp);
	
	for(int i=1,j=1;i<=q;i++){
		while(e[j].w<=a[i].w&&j<=m){
			merge(e[j].u,e[j].v);
			++j;
		}
		ans[a[i].id]=(find(a[i].u)==find(a[i].v)); 
	}
	
	for(int i=1;i<=q;i++){
		if(ans[i]){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
	}
	
	return 0;
}