P1955,90分,#2RE了,求大佬指点
  • 板块学术版
  • 楼主Lycdeer
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 09:45
  • 上次更新2024/8/20 10:37:03
查看原帖
P1955,90分,#2RE了,求大佬指点
1088782
Lycdeer楼主2024/8/20 09:45
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,e;
}a[100005];
int f[100005];
bool cmp(node a,node b){
	return a.e>b.e;
}
bool ans[100];
int find(int x){
	if(f[x]==x||f[x]==0) return x;
	return f[x]=find(f[x]);
}
void hb(int x,int y){
	int fx=find(x),fy=find(y);
	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));
		for(int j=1;j<=n;j++) cin>>a[j].x>>a[j].y>>a[j].e;
		sort(a+1,a+n+1,cmp);
		bool f=false;
		for(int j=1;j<=n;j++)
			if(a[j].e==1) 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 09:45
加载中...