pku1733 Parity game(离散化+并查集拓展应用)

时间：2011-05-11 来源：枕边梦

这题目让我郁闷了好久的说，首先就是离散化过程，区间大小和测试的例子相差太大，十分有必要进行离散化，这里就出现一个问题了，这道题目而已，离散化过程需要保持数据之间的相对大小吗？需要跟不需要相差很多吗？差别的话，当然很大啦，如果不需要保持数据的相对大小，那么，在映射过程中就可以直接将映射值放入运算了，而如果需要呢？这时，我们需要先将读入的数据保存，再排序，进入hash，或者使用map函数，这一过程就用了好多内存了和时间了

为什么不需要保持数据的相对大小呢？因为我们用的是并查集，每个节点都有一个根节点，这里就是关键了，根节点是如何选的呢？呵呵，其实仔细想想，我们如何判断一个区间内1 的个数的奇偶性呢？利用的区间端点跟根节点的关系推出来，而这里，根节点具体是哪一个并不知道，这个要看输入数据了，这时我们发现，端点大小跟该区间内1的个数的奇偶性有关系吗？没关系对吧，我们记录的是，出现过的节点到根节点之间的1的个数的奇偶性

还有一道类似的题目，也贴出了吧，hdu3038

#include<stdio.h>
#define MAXN 200010
int f[MAXN],r[MAXN];
int find(int x)
{
        if(x==f[x])
                return f[x];
        int t=find(f[x]);
        r[x]=r[x]+r[f[x]];
        f[x]=t;
        return f[x];
}
int fun(int x,int y)
{
        if(x>y)
                return x-y;
        else y-x;
}
int Union(int x,int y,int sum)
{
        int a=find(x);
        int b=find(y);
        if(a==b)
        {
                if(fun(r[x],r[y])==sum)
                        return 0;
                else return 1;
        }
        else 
        {
                f[a]=b;
                r[a]=r[y]+sum-r[x];
                return 0;
        }
}
int main()
{
        int n,m,i,ans,a,b,s;
        while(scanf("%d %d",&n,&m)!=EOF)
        {
                ans=0;
                for(i=0;i<=n;i++)
                {
                        f[i]=i;
                        r[i]=0;
                }
                for(i=1;i<=m;i++)
                {
                        scanf("%d %d %d",&a,&b,&s);
                        a--;
                        if(Union(a,b,s))
                                ans++;
                }
                printf("%d\n",ans);
        }
        return 0;
}

pku1733

#include<iostream>
#include<map>
#include<stdio.h>
using namespace std;
#define MAXN 10010
int f[MAXN],r[MAXN];
//f[]记录父节点，r[]记录与根节点直接1的奇偶性
void init()
{
        int i;
        for(i=0;i<=10001;i++)
        {
                f[i]=i;
                r[i]=0;
        }
}//还是老步骤，初始化并查集
int find(int x)
{
        if(f[x]==x)
                return x;
        int t=find(f[x]);
        r[x]=(r[x]+r[f[x]])%2;//这里的话，别当成什么公式吧，可以这样 想，根据当前节点与父节点的关系，以及父节点与根节点的关系，推出当前节点与根节点的关系
        f[x]=t;
        return f[x];
}//压缩路径
int Union(int x,int y,int d)
{
        int a=find(x);
        int b=find(y);
        if(a==b)
        {
                if((r[x]+r[y])%2==d)//这个也好理解吧，并查集做了这么多了
                        return 1;
                else return 0;
        }
        else {
                f[a]=b;
                r[a]=(r[x]+r[y]+d)%2;//这一步的话，涉及四个节点了，根据其他三个节点之间的关系，觉得第四个节点与根节点的关系
                //剩下的还是在压缩路径的过程中解决
                return 1;
        }
}
int main()
{
        int i,j,n,m,a,b,add=0;
        int x,y,d;
        char s[5];
        scanf("%d %d",&n,&m);
        init();
        map<int,int> mm;
        for(i=1;i<=m;i++)
        {
                scanf("%d %d %s",&a,&b,s);
                a--;
                if(mm.find(a)==mm.end())//判定a是否已经映射过了
                {
                        mm[a]=add++;
                }
                x=mm[a];
                if(mm.find(b)==mm.end())
                {
                        mm[b]=add++;
                }
                y=mm[b];
                if(s[0]=='o')
                        d=1;
                else d=0;
                if(Union(x,y,d)==0)//其实，测试数据只有一个，所以发现矛盾即可立即退出了
                        break;
        }
        printf("%d\n",i-1);
        return 0;
}