社区讨论
关于图论的一个问题
学术版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo20po5m
- 此快照首次捕获于
- 2023/10/23 06:05 2 年前
- 此快照最后确认于
- 2023/11/03 06:29 2 年前
在一个有向无环图 中,给节点分别标上 的编号。然后我们有一些小球。小球的移动是有规则的。每个节点都有一个“记忆”,表示上一次小球通过了这个节点去向了几号节点。如果没有小球通过过,“记忆”为 。如果某个“时刻” 号节点有小球,那么下一个“时刻”小球会去向比“记忆”中的节点编号大的且存在一条有向边 的 号节点。如果没有比“记忆”中的节点编号大的可到达的节点,就重新从可到达的编号最小的节点开始。如果当前节点有小球,且没有可到达的节点。那么小球视为被此节点“接受”。小球从第 “时刻”开始,每个“时刻”都会在 号节点放置一个小球。
可以举个例子,即一个简单的图 。从第 时刻开始,每一个时刻 号节点上都有一个小球。同时从第 个“时刻”开始,每一个“时刻” 号节点都会“接受”一个来自 号节点的小球。
再比如说一个图 ,这个时候 号节点给出的球会在 号节点和 号节点之间“反复横跳”,并被“接受”。如果是图 ,可以得到 号节点从第 个“时刻”开始,每奇数个“时刻”会“接受” 个小球,偶数个时刻不接受小球。
我的问题是,能否编写比较快速的程序,能够预测第 时刻每个节点“接受”的小球数量?或者有没有数学方法可以得到答案?如果有这样的题目(不要类似,要一模一样),我也可以去看题解的。
回复
共 2 条回复,欢迎继续交流。
正在加载回复...