P188 沙堆
沙堆
题目描述
阿贝尔沙堆模型是一个著名的显示自组织临界性的动力系统。自从 Per Bak、Chao Tang 和 Kurt Wiesenfeld 在 1987 年的一篇论文中提出该模型以来,对它的研究已经持续了几十年。沙堆预测因其优美的代数结构以及与负载平衡和内部扩散受限聚集等模型的去随机化等应用的相关性,在物理学、计算机科学和数学领域受到广泛关注。沙堆模型与许多其他模型和物理现象有关,如转子路由模型、雪崩模型等。
在沙堆模型中,我们给定了一个无向图 ,其顶点索引为 至 。我们还给出了 个整数 ,其中 表示最初在顶点 上放置了 个筹码。我们每一轮都会选取一个任意顶点 ,使得 上的筹码数不小于连接 的边数,记为 。对于 的每个邻居,它将从 接收一个筹码。因此, 将失去 个筹码。这个过程称为 "发射 "或 "推翻"。发射会一直发生,直到没有顶点 拥有至少 个筹码。
可以证明发射的顺序不会影响结果。同时,发射也有可能永远不会终止。这种情况被称为 "循环"。现在给你一个小群和初始筹码数。请判断该实例是否为递归实例。如果不是,请分别输出每个节点的最终筹码数。



