70分求助!!
查看原帖
70分求助!!
553176
coding_hong楼主2021/12/19 18:42
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#define ll long long

const int maxn=1000007;
using namespace std;
ll l=-1,t,n,book[maxn*3],f[maxn];
struct edge{
	ll a,b,x;
}e[maxn];

ll get(ll x)
{
	if(f[x]==x)return x;
	return f[x]=get(f[x]);
}
bool cmp(edge yeshou,edge xianbei)
{
	return yeshou.x>xianbei.x;
}
int main()
{
	freopen("P1955_2.in","r",stdin);
	//freopen("P1955_my.out","w",stdout);
	scanf("%lld",&t); 
	while(t--)
	{
		for(int i=1;i<=n;i++)f[i]=i;
		memset(book,0,sizeof(book));
		memset(f,0,sizeof(f));
		memset(e,0,sizeof(e));
		l=-1;
		bool flag=1;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		{
			ll a,b,x;
			scanf("%lld %lld %lld",&a,&b,&x);
			e[i].a=a,e[i].b=b,e[i].x=x;
			book[++l]=a;book[++l]=b;
		} 		
		sort(book,book+l);
		int reu=unique(book,book+l)-book;
		for(int i=1;i<=n;i++)
		{
			e[i].a=lower_bound(book,book+reu,e[i].a)-book;
			e[i].b=lower_bound(book,book+reu,e[i].b)-book;
		}
		sort(e+1,e+n+1,cmp);
		
		for(int i=1;i<=n;i++)
		{
			int r1=get(e[i].a);
			int r2=get(e[i].b);
			if(e[i].x)f[r1]=r2;
			else if(r1==r2)
			{
				printf("NO\n");
				flag=0;
				break;
			}
		}		
		if(flag)printf("YES\n");
	}		
	return 0;
	 
}


2021/12/19 18:42
加载中...