CF891C Envy

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define maxn 550000
#define rep(x,y,z) for(register int x = y ; x <= z ; x ++)
#define per(x,y,z) for(register int x = y ; x >= z ; x --)
using namespace std ;
int read() {
    int x = 0 ,  f = 1 ; char s = getchar() ;
    while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
    while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;}
    return x*f ;
}
int fa[maxn] ;
int find(int x) {
    if(fa[x] != x) fa[x] = find(fa[x]) ;
    return fa[x] ;
}
void merge(int x ,int y) {
    x = find(x) , y = find(y) ;
    fa[y] = x ;
}
struct dy{
    int x , y ,z , id , tx, ty ;
    int operator < (const dy x)const {
        return z < x.z ;
    }
}a[maxn] ;

bool cmp(dy x , dy y) {
    return x.id < y.id ;
}
int n ,m  ;
int main () {
    n = read() , m = read() ;
    rep(i,1,n) fa[i] = i ;
    rep(i,1,m) {
        a[i].x = read() ;
        a[i].y = read() ;
        a[i].z = read() ;
        a[i].id = i ;
    }
    sort(a+1,a+1+m) ;
    a[0].z = -1 ;
    for(int i = 1 ; i <= m ;) {
        int j = i ;
        do {
            a[j].tx = find(a[j].x) ;
            a[j].ty = find(a[j].y) ;
            j ++ ;
        }while(j <= m && a[j].z == a[j-1].z) ;
        while(i < j) {
            while(find(a[i].x) == find(a[i].y) && i < j) i ++ ;
            if(i < j) merge(a[i].x , a[i].y ) ;
        }
    }
    int q = read() ;
    sort(a+1,a+1+m,cmp) ;
    rep(i,1,n) fa[i] = i ;
    while(q --) {
        int k = read() ;
        vector<dy>v ;
        rep(i,1,k) {
            int x = read() ;
            v.push_back({a[x].tx,a[x].ty,a[x].z}) ;
        }
        sort(v.begin(),v.end()) ;
        int flag = 1 ;
        for(int i = 0 , sz = v.size()-1 ; i <= sz && flag;) {
            if(v[i].x == v[i].y) {
                flag = 0 ;
                break ;
            }
            merge(v[i].x,v[i].y) ;
            int j = i + 1 ;
            while(j <= sz && v[j].z == v[i].z) {
                if(find(v[j].x) == find(v[j].y)) {
                    flag = 0 ;
                    break ;
                }merge(v[j].x,v[j].y) ;j ++ ;
            }while(i < j) {
                fa[v[i].x] = v[i].x ;
                fa[v[i].y] = v[i].y ;
                i ++ ;
            }
        }
        puts(flag ? "YES" : "NO") ;
    }
    return 0 ;
}

CF891C Envy

原文：https://www.cnblogs.com/lyt020321/p/11632077.html