题解 P1955 【[NOI2015]程序自动分析】

· · 题解

我作为一个蒟蒻居然A了QAQ，那就详细说一说

并查集

并查集实际上是一个森林。

令一数组f记录每一个结点的爸爸，第i个结点的爸爸是f_i，当f_i=i时，也就是说它的爸爸是自己，即没有爸爸时，它就是根结点。

并查集有两种基本操作：find和merge

find

俗称找爸爸。

本人习惯于使用递归实现

int find(int x)
{
    if(f[x]==x) return x;
    else return find(f[x]);
}

即可，比较简单请自行理解

merge

合并两棵树，直接把第2棵树的最早的祖先的爸爸改为第1棵树的最早的祖先

代码很简单：

void merge(int a,int b)
{
    f[find(a)]=find(b);
}

路径压缩

按照上面的代码，很快这棵树就会变成类链的东西，那么每一次find操作的耗时就不能接受了。

我们考虑在整个过程中，我们只需要利用一个结点的最早的祖先，那么只需要每次find操作过程中，把这个结点的爸爸改成它最早的祖先。

只需要把find操作的代码稍作修改即可。

int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}

离散化

离散化，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

来自百度（反正我一开始没看懂）

讲通俗一点，就是把一个可以很大的数据排个序，去个重，放在新的数组里，每次用二分找它在新数组的位置。

并查集和离散化

把x离散化之后，对于每一个x进行并查集操作

将条件转化为并查集的基本操作

两个x相等，则相当于在一个集合里，否则不在一个集合。

细节

进行限制条件的判断前，先按e排个序，1在前面，0在后面，为什么请自己思考

代码

直接复制你会爆零的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100007
#define maxnt 1000000007
struct node{
    int a,b,e;
}a[maxn];
int ttttt,f[maxn*2],x[maxn*2],n,lsh[maxn*2],nn,wz[maxn*2];
bool flag;
void mak()
{
    for(register int i=1;i<=nn;i++) f[i]=i;
}
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
bool comp(int a,int b)
{
    return a<b;
}
bool cmp(node a,node b)
{
    return a.e>b.e;
}
int er(int zz)
{
    int l=1,r=nn,m;
    while(l<=r)
    {
        m=(l+r)/2;
        if(lsh[m]==zz) return m;
        if(zz>lsh[m]) l=m+1;
        else r=m-1;
    }
    return zz;
}
int mian()
{
    scanf("%d",&ttttt);
    while(ttttt--)
    {
        scanf("%d",&n);
        nn=0;
        flag=0;
        for(register int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].e);
            x[i*2-1]=a[i].a,x[i*2]=a[i].b;
        }
        sort(x+1,x+2*n+1,comp);
        for(register int i=1;i<=2*n;i++)
        {
            if(x[i]!=x[i-1])
            {
                lsh[++nn]=x[i];
//              wz[i]=nn;
            }
//          else wz[i]=wz[i-1];
        }
        mak();
        sort(a+1,a+n+1,cmp);
        for(register int i=1;i<=n;i++)
        {
            if(a[i].e)
            {
                int aaa=find(er(a[i].a)),bbb=find(er(a[i].b));
                if(aaa!=bbb) f[aaa]=bbb;
            }
            else
            {
                int aaa=find(er(a[i].a)),bbb=find(er(a[i].b));
                if(aaa==bbb)
                {
                    printf("NO\n");
                    flag=1;
                    break;
                }
            }
        }
        if(!flag) printf("YES\n");
    }

    return 0;
}