首页 > 代码库 > POJ 1988 Cube Stacking

POJ 1988 Cube Stacking

2024-07-19 04:30:03   216人阅读

题意：有编号为1~N的N个小木块，有两种操作

  1. M x y 将木块x所在的堆放到木块y所在的堆的上面
  2. C x 询问木块x下面有多少块木块

代码巧妙就巧妙在GetParent函数中在进行路径压缩的同时，也计算好了该木块对应的under值

这个需要好好体会

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 30000 + 10; 8 int parent[maxn], under[maxn], sum[maxn]; 9 10 int GetParent(int a)11 {12     if(parent[a] == a)13         return a;14     int t = GetParent(parent[a]);15     under[a] += under[parent[a]];16     parent[a] = t;17     return t;18 }19 20 void Merge(int a, int b)21 {22     int pa = GetParent(a);23     int pb = GetParent(b);24     if(pa == pb)    return;25     parent[pb] = pa;26     under[pb] = sum[pa];27     sum[pa] += sum[pb];28 }29 30 int main(void)31 {32     #ifdef LOCAL33         freopen("1988in.txt", "r", stdin);34     #endif35 36     for(int i = 1; i < maxn; ++i)37     {38         parent[i] = i;39         under[i] = 0;40         sum[i] = 1;41     }42     int n;43     scanf("%d", &n);44     getchar();45     for(int i = 0; i < n; ++i)46     {47         char p;48         scanf("%c", &p);49         if(p == ‘M‘)50         {51             int a, b;52             scanf("%d%d", &a, &b);53             getchar(); 54             Merge(b, a);55         }56         else57         {58             int a;59             scanf("%d", &a);60             getchar();61             GetParent(a);62             printf("%d\n", under[a]);63         }64     }65     return 0;66 }
代码君

 

POJ 1988 Cube Stacking


联系
我们