10 pts求调
查看原帖
10 pts求调
496009
黄舀啊楼主2022/6/24 18:52
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN = 1e6+10;

ll fa[MAXN<<1];
ll t,n;
ll book[MAXN*3];

struct node{
	ll a,b,c;
}pro[MAXN];

inline bool cmp(node x,node y){
	return x.c>y.c;
}

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

inline ll get(int x){
	if(x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

inline void merge(int x,int y){
	fa[get(x)] = get(y);
}

int main(){
	
	t = read();
	while(t--){
		memset(book,0,sizeof(book));
		memset(pro,0,sizeof(pro));
		memset(fa,0,sizeof(fa));
		int tot = -1;
		n = read();
		bool flag = 1;
		for(int i=1 ; i<=n ; i++)
			pro[i].a = read(),pro[i].b = read(),pro[i].c = read(),book[++tot] = pro[i].a,book[++tot] = pro[i].b;
		sort(book,book+tot);
		int reu = unique(book,book+tot)-book;
		for(int i=1;i<=n;++i){
           pro[i].a=lower_bound(book,book+reu,pro[i].a)-book;
           pro[i].b=lower_bound(book,book+reu,pro[i].b)-book;   
        } 
        for(int i=1 ; i<=2*reu ; i++)
			fa[i] = i;
		sort(pro+1,pro+1+n,cmp);
		for(int i=1 ; i<=n ; i++){
			if(pro[i].c == 1){
				if(get(pro[i].a) == get(pro[i].b+n) || get(pro[i].a+n) == get(pro[i].b)){
//					cout << "NO" << endl;
					flag = 0;
					break;
				} else {
					merge(pro[i].a,pro[i].b);
					merge(pro[i].a+n,pro[i].b+n);
				}
			} else {
				if(get(pro[i].a) == get(pro[i].b) || get(pro[i].a+n) == get(pro[i].b+n)){
//					cout << "NO" << endl;
					flag = 0;
					break;
				} else {
					merge(pro[i].a,pro[i].b+n);
					merge(pro[i].a+n,pro[i].b);
				}
			}
		}
		if(flag == 1)
			cout << "YES" << endl;
		else 
			cout << "NO" << endl;
	}
	
	return 0;
}
2022/6/24 18:52
加载中...