yes you do

yes i do
posts - 4, comments - 2, trackbacks - 0, articles - 0

PKU1988Cube Stacking 并查

Posted on 2009-05-30 15:35 chenweiwei 阅读(263) 评论(0)  编辑 收藏 引用
Cube Stacking

Cube StackingFarmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.
-------------------
仍然是并查,仍然是想了很久,仍然是参考了别人的代码才明白,学了这么久,真的会怀疑自己的智商了。

PKU1988仍然是并查的题目,没有特意说要找并查的题目来做,只是偶尔到了某一页发现某一道题目可以用并查来做,于是载下去了。
题意:
其实题意比较好理解,两个命令:如果是c命令则算出输出的cube X下面有多少个立方体,如果是M命令,则把cube Y所在的集合中的全部立方体放入cube X 所在的立方集合下。
初始化:
定义一个结构体,保存一个cube的根cube存于parent中,保存cube上面的立方数于up中,保存cube的下面的立方数于down中。

struct node
{
    
int parent;
    
int up;
    
int down;
}
Node[SIZE];

void Init(int nt)
{
    
for (int i=0; i <= nt;i++)
    
{
        Node[i].parent
=i;  //根为自己
        Node[i].down=1;    //初始化设为1只是为了计算的方便,到后面会减1
        Node[i].up=0;      //初始化高上面没有立方体。
    }

}


合并操作:
合并的时候找两个cube的根结点,并且对要结点的up及dow变量进行操作。具体看代码注释

int UnionSet(int i,int j)
{
    i
=FindSet(i);
    j
=FindSet(j);
    Node[j].up
=Node[i].down;    //i下面的cube都变成了j上面的cube,归入Node[j].up
    Node[i].down+=Node[j].down; //能够想像,j下面的所有cube同时也都归入i中
    Node[j].parent=i;           //两个集合合并成一个集合 i为根
    return 0;
}


查询操作:
查询的时候找结点父亲,并且找父亲结点的上面cube数归入结点上面cube数中,如果父亲结点有根结点,则继续查找(哇,很难表达啊)。
int FindSet(int i)
{
    
int m;
    
if (Node[i].parent!=i)
    
{
        m
=Node[i].parent;
        Node[i].parent
=FindSet(Node[i].parent); //找父亲结点的父亲结点
        Node[i].up+=Node[m].up;                 //将父亲结点的up归入结点的up中
    }

    
return Node[i].parent;
}

主函数:
int main(int argc, char* argv[])
{
//    freopen("in.txt","r",stdin);
    int p;
    scanf(
"%d",&p);
    
char op;
    Init(SIZE);
    
while(p--)
    
{
        getchar();
        op
=getchar();
        
if(op=='M')
        
{
            
int x,y;
            scanf(
"%d %d",&x,&y);
            UnionSet(x,y);
        }

        
else if(op=='C')
        
{
            
int x,y;
            scanf(
"%d",&x);
            y
=FindSet(x);
            printf(
"%d\n",Node[y].down-Node[x].up-1); //这里需要减1
        }

    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理