50分求助
查看原帖
50分求助
692647
tanghg楼主2022/11/10 13:45
#include<iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll n,f[MAXN];
struct node{
    ll u,v,w;
}a[MAXN];
void init(){
    ll q[MAXN],sz=0;
    for (int i = 1; i <=n ; ++i) {
        q[++sz]=a[i].u;
        q[++sz]=a[i].v;
    }
    sort(q+1,q+n+1);
    ll new_n= unique(q+1,q+n+1)-q;
    for (int i = 1; i <=n; ++i) {
        a[i].u= lower_bound(q+1,q+new_n+1,a[i].u)-q;
        a[i].v= lower_bound(q+1,q+new_n+1,a[i].v)-q;
    }
}
ll find(ll x){
    while (x!=f[x]){
        f[x]=f[f[x]];
        x=f[x];
    }
    return x;
}
void merge(ll u,ll v){
    ll U= find(u),V= find(v);
    f[U]=V;
}
bool cmp(node A,node B){
    return A.w>B.w;
}
int main(){
    ll t;
    cin>>t;
    for (int i = 1; i <=t ; ++i) {
        cin>>n;
        for (int j = 1; j <=n+4 ; ++j) {
            f[j]=j;
        }
        for (int j = 1; j <=n ; ++j) {
            cin>>a[j].u>>a[j].v>>a[j].w;
        }
        init();
        sort(a+1,a+n+1,cmp);
        bool good= true;
        for ( ll j =1 ; j<=n ; ++j) {
            if(a[j].w==1){
                merge(a[j].u,a[j].v);
            }else{
                if(find(a[j].u)== find(a[j].v)){
                    cout<<"NO"<<endl;
                    good= false;
                    break;
                }
            }
        }
        if(good){
            cout<<"YES"<<endl;
        }
    }
    return 0;
}
2022/11/10 13:45
加载中...