POJ--1988 cube stacking-蒲公英云

POJ--1988 cube stacking

    关于这道题目，本来想到的是既然是搬箱子到另一堆上，那么我只要知道某一堆的底部箱子，和顶部的箱子即可。以底部的箱子为父亲节点，则顶部箱子就是以该箱子为父亲节点的到其距离最大的点。  
    因为每个节点到其根节点的距离是保存在各自的rank数组里的，所以应该是可行的。但是愚笨的我偏偏要把每一堆的点都要find一遍，结果当然TLE。  
    1.方法行不通只能改进了，参考了别人的代码；把一堆最上面的箱子作为根，用数组rank表示x到其根节点的距离，用count\[x\]表示以x为根节的箱子的个数，则x下面的箱子个数很显然就是count\[ fx \] -rank\[x\]-1;
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=30005;
int f[maxn],rank[maxn],count[maxn]; 
void initial()
{
    for(int i=0;i<maxn;i++)
    {
        f[i]=i;count[i]=1;
    }
    memset(rank,0,sizeof(rank));
}
int find(int x)
{
    if(x==f[x])return x;
    int r=f[x];
    r=find(r);
    rank[x]+=rank[f[x]];
    return f[x]=r;
}
void Union(int x,int y)
{
    int tx=find(x),ty=find(y);
    rank[ty]=count[tx];
    count[tx]+=count[ty];
    f[ty]=tx;
}
int main()
{
    int P;
    scanf("%d",&P);
    initial();
    while(P--)
    {
        char s[5];int x,y;
        scanf("%s",s);
        if(s[0]=='M')
        {
            scanf("%d%d",&x,&y);
            Union(x,y);
        }
        else if(s[0]=='C')
        {
            scanf("%d",&x);
            int fx=find(x);
            printf("%d\n",count[fx]-rank[x]-1);
        }
    }
    return 0;
}

2.这一种和上一种类似，不过是以箱子堆底部为根节点，rank[ x ]表示x到其根节点的距离，nNum[ x ]表示以x为根节点的堆的箱子数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = 30010;
int nSets[MAX];
int nNum[MAX];
int nRank[MAX];
void MakeSets(int nN)
{
    for (int i = 0; i < nN; ++i)
    {
        nSets[i] = i;
        nNum[i] = 1;
        nRank[i] = 0;
    }
}
int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nRank[nI] += nRank[nPre];
    }
    return nSets[nI];
}
void Move(int nX, int nY)
{
    int nA = FindSet(nX);
    int nB = FindSet(nY);
    if (nA != nB)
    {
        nSets[nA] = nB;
        nRank[nA] += nNum[nB];
        nNum[nB] += nNum[nA];
    }
}
int main()
{
    int nP;
    char szOper[10];
    int nX, nY;
    scanf("%d", &nP);
    MakeSets(MAX);
    while (nP--)
    {
        scanf("%s", szOper);
        if (szOper[0] == 'M')
        {
            scanf("%d%d", &nX, &nY);
            Move(nX, nY);
        }
        else
        {
            scanf("%d", &nX);
            FindSet(nX);
            printf("%d\n", nRank[nX]);
        }
    }
    return 0;
}

3.这算是第二种方法的优化吧，去掉了一个数组，思想很巧妙。利用了f[ x ]的负值表示该节点为根节点和这一堆得箱子的个数…….，也就是去掉了count，其中nr数组为该箱子到其根节点的距离。

#include <iostream>
#include <cstdio>
using namespace std;
int cube[30330],nr[30330];
int n;
void make_set()
{
    for(int i=0;i<=30030;++i)
    {
        cube[i] = -1;
        nr[i] = 0;
    }
}
int find_set(int x)
{
    int tmp = cube[x];
    if(cube[x]<0)
        return x;
    cube[x] = find_set(cube[x]);
    nr[x] += nr[tmp];
    return cube[x];
}
void union_set(int n1,int n2)
{
    int root1 = find_set(n1);
    int root2 = find_set(n2);
    int tmp = cube[root1];
    cube[root1] = root2;
    nr[root1] =nr[root1] - cube[root2];
    cube[root2] += tmp;
}
int main()
{
    int i,j,root1,root2,n1,n2;
    char ch[1];
    cin>>n;
    make_set();
    while(n--)
    {
        scanf("%s ",ch);    
        if(ch[0]=='M')
        {
            scanf("%d%d",&n1,&n2);
                union_set(n1,n2);
        }else if(ch[0]=='C')
        {
            scanf("%d",&n1);
            int tmp =find_set(n1);
            printf("%d\n",nr[n1]);
        }
    }
    return 0;
}