并查集+离散化,仅AC了第一个点,后面大部分RE,也有少量WA,求大佬qwq
查看原帖
并查集+离散化,仅AC了第一个点,后面大部分RE,也有少量WA,求大佬qwq
788115
chocococoooo楼主2024/3/11 12:52
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int N = 300010;//离散化后最多有2n个下标
typedef long long LL;

int p[N];
typedef struct Constrain{
    LL x;
    LL y;
    LL z;
} constrain;
vector<LL> alls;
vector<constrain> record;

bool cmp(constrain x,constrain y){
    return x.z>=y.z;
}

int findAlls(LL x){//找x在alls数组中的位置
    int l=0;
    int r=alls.size()-1;
    while(l<r){
        int mid=(l+r)>>1;
        if(alls[mid]>=x){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    return r+1;//1-alls.size()
}

int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        alls.clear();
        record.clear();
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            LL x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            alls.push_back(x);
            alls.push_back(y);
            record.push_back({x,y,z});
        }
        //对x,y进行离散化
        sort(alls.begin(),alls.end());
        alls.erase(unique(alls.begin(),alls.end()),alls.end());
        //完成find函数
        //并查集初始化
        for(int i=1;i<=alls.size();i++){
            p[i]=i;
        }
        sort(record.begin(),record.end(),cmp);//TODO:关键点:按照z进行排序,即先连接所有=,在用不等号排除
        //并查集连接:开始求解
        bool flag=true;
        for(constrain cur : record){
            LL x=cur.x;
            LL y=cur.y;
            LL z=cur.z;
            int px= find(findAlls(x));
            int py=find(findAlls(y));
            if(z==1){
                if(px!=py){
                    p[x]=py;
                }
            }else if(z==0){
                if(px==py){
                    flag=false;//在一个并查集中即矛盾
                    break;
                }
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
2024/3/11 12:52
加载中...