70分求助!!!
查看原帖
70分求助!!!
383601
shijihong楼主2021/7/1 13:45
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int s[2000005],i;
struct node{
	int x,y,e;
	bool operator <(const node &rhs) const{return e>rhs.e;}
};
node a[1000005];
int dfs(int x){
	if(x!=s[x]) s[x]=dfs(s[x]);
	return s[x];
}
void merge1(int x,int y){
	x=dfs(x),y=dfs(y);
	s[y]=x;
}
map<int,bool> vis;
map<int,int> pos;
bool operate(int n){
	vis.clear();
	pos.clear();
	for(i=1;i<=n;i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].e);
		vis[a[i].x]=vis[a[i].y]=1;
	}
	int j=1;
	for(map<int,bool>::iterator it=vis.begin();it!=vis.end();it++,j++)pos[it->first]=j;
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++) s[i]=i;
	i=0;
	for(i=1;i<=n and a[i].e==1;i++) merge1(pos[a[i].x],pos[a[i].y]);
	bool flag=true;
	for(;i<=n;i++)
		if(dfs(pos[a[i].x])==dfs(pos[a[i].y])){
			flag=false;
			break;
		}
	return flag;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		if(operate(n)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
2021/7/1 13:45
加载中...