POJ--1988 cube stacking

╰+哭是因爲堅強的太久メ 2022-08-11 00:56 170阅读 0赞

关于这道题目，本来想到的是既然是搬箱子到另一堆上，那么我只要知道某一堆的底部箱子，和顶部的箱子即可。以底部的箱子为父亲节点，则顶部箱子就是以该箱子为父亲节点的到其距离最大的点。  
        因为每个节点到其根节点的距离是保存在各自的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;
    }