P1955,#2MLE,求大佬帮助
  • 板块学术版
  • 楼主Lycdeer
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 14:22
  • 上次更新2024/8/20 16:18:47
查看原帖
P1955,#2MLE,求大佬帮助
1088782
Lycdeer楼主2024/8/20 14:22
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,e;
}a[100005];
int f[100005],mp[2000005];
bool cmp(node a,node b){
	return a.e>b.e;
}
bool ans[100];
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void hb(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) f[fx]=fy;
}
int main(){
	int T; cin>>T;
	for(int i=1;i<=T;i++){
		int n; cin>>n;
		memset(f,0,sizeof(f));
		memset(a,0,sizeof(a));
		memset(mp,0,sizeof(mp));
		int tmp=0;
		for(int j=1;j<=n;j++){
			cin>>a[j].x>>a[j].y>>a[j].e;
			mp[++tmp]=a[j].x;
			mp[++tmp]=a[j].y;
		}
		sort(mp+1,mp+tmp+1);
		int len=unique(mp+1,mp+tmp+1)-mp;
		for(int j=1;j<=n;j++){
			a[j].x=lower_bound(mp+1,mp+len+1,a[j].x)-mp;
			a[j].y=lower_bound(mp+1,mp+len+1,a[j].y)-mp;
		}
		for(int j=1;j<=len;j++) f[j]=j;
		sort(a+1,a+n+1,cmp);
		bool f=false;
		for(int j=1;j<=n;j++){
			if(a[j].e) hb(a[j].x,a[j].y);
			else{
				int fx=find(a[j].x),fy=find(a[j].y);
				if(fx==fy){
					ans[i]=false;
					f=true;
					break;
				}
			}
		}
		if(!f) ans[i]=true;
	}
	for(int i=1;i<=T;i++)
		if(ans[i]) cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	return 0;
}
2024/8/20 14:22
加载中...