问题标题: 洛谷:P1955 程序自动分析

0
0
已解决
赵逸凡
赵逸凡
初级启示者
初级启示者

一道看起来很简单的题目,但不知道怎么错了。

#include<iostream>
#include<queue>
using namespace std;
long long n,m,fa[1000010<<1],f,t;
struct node{
    long long a1,x1,y1;
    bool operator<(const node& tmp)const{
        return a1<tmp.a1;
    }
};
priority_queue<node> q;
void init()
{
    for(long long i=1;i<=n;i++)
        fa[i]=i;
}
long long find(long long x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void unite(long long x,long long y)
{
    x=find(x);
    y=find(y);
    fa[x]=y;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        init();
        for(long long i=1;i<=n;i++)
        {
            long long x,y,a;
            cin>>x>>y>>a;
            q.push((node){a,x,y});
        }
        while(!q.empty())
        {
            node h=q.top();
            q.pop();
            long long a=h.a1;
            long long x=h.x1;
            long long y=h.y1;
            if(a==1)    
                unite(x,y);
            if(a==0)
            {
                x=find(x);
                y=find(y);
                if(x==y)
                    f=1;
            }
        }
        if(f==1)
            cout<<"NO\n";
        if(f==0)
            cout<<"YES\n";
        f=0;
    }
    return 0;
}

评测结果:

我的思路就是用堆来将相等关系式放在前面,不等关系式放在后面,再用并查集判断矛盾,然而为什么WA 4个点?


0
已采纳
刘景程
刘景程
新手光能
新手光能

题姐姐说了要用没有学过的离散化

所以。。。空间会炸的,只能过5个点

0
0
赵逸凡
赵逸凡
初级启示者
初级启示者

@黄子扬 @李源徽 @刘景程 

 

 

 

0
张天璨
张天璨
新手天翼
新手天翼

膜拜膜拜,我实在不会!

0
赵逸凡
赵逸凡
初级启示者
初级启示者

@余彦文 emmmm...数组大小改成5024×5024后还是RE一个点

 

我要回答