P1955 NOI2015程序自动分析


这道题其实就是把相等的两个点用并查集维护,首先通过排序把相等的放在前面建立集合,然后再通过不等判断是否处在同一集合,由于ij规模过大,要先离散化

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000005;
int t,tot,n;
int b[maxn],fa[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
struct node{
    int x,y,e;
}a[maxn];
bool cmp(node a,node b)
{
    return a.e>b.e;
}
int main()
{
    t=read();
    while(t--)
    {
        bool pan=true;
        tot=0;
        int n=read();
        for(int i=1;i<=n;i++)
        {
            a[i].x=read();
            a[i].y=read();
            a[i].e=read();
            b[++tot]=a[i].x;
            b[++tot]=a[i].y;
        }
        sort(a+1,a+1+n,cmp);
        sort(b+1,b+1+tot);
        tot=unique(b+1,b+tot+1)-(b+1);
        for(int i=1;i<=tot;i++) fa[i]=i;
        for(int i=1;i<=n;i++)
        {
            a[i].x=lower_bound(b+1,b+tot+1,a[i].x)-b;
            a[i].y=lower_bound(b+1,b+tot+1,a[i].y)-b;
            if(a[i].e) fa[find(a[i].x)]=find(a[i].y);
            else if(find(a[i].x)==find(a[i].y))
            {
                pan=false;
                break;
            }
        }
        if(pan) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1196 NOI2002银河英雄传说 P1196 NOI2002银河英雄传说
通过带权并查集维护距离 #include<bits/stdc++.h> using namespace std; const int maxn=30010; inline int read() { int x=0,t=1;c
2019-07-05
下一篇 
POJ2689Prime Distance POJ2689Prime Distance
这是区间筛素数的模板,由于l r过大,之间用埃筛一定会超时,由于r-l在接受范围内,所以先把1-根号r的素数预处理一遍,然后再用p*i统计l-r内的素数,注意l=1要特判 #include<cstdio> #include<c
2019-07-05
  目录