关于图论的一个问题
  • 板块学术版
  • 楼主66xyyd
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/1 20:10
  • 上次更新2023/11/3 06:29:13
查看原帖
关于图论的一个问题
946515
66xyyd楼主2023/8/1 20:10

在一个有向无环图 GG 中,给节点分别标上 1,2,…,n1,2,\dots,n 的编号。然后我们有一些小球。小球的移动是有规则的。每个节点都有一个“记忆”,表示上一次小球通过了这个节点去向了几号节点。如果没有小球通过过,“记忆”为 −1-1。如果某个“时刻” ii 号节点有小球,那么下一个“时刻”小球会去向比“记忆”中的节点编号大的且存在一条有向边 i→ji \to j 的 jj 号节点。如果没有比“记忆”中的节点编号大的可到达的节点,就重新从可到达的编号最小的节点开始。如果当前节点有小球,且没有可到达的节点。那么小球视为被此节点“接受”。小球从第 11 “时刻”开始,每个“时刻”都会在 11 号节点放置一个小球。

可以举个例子,即一个简单的图 1→21 \to 2。从第 11 时刻开始,每一个时刻 11 号节点上都有一个小球。同时从第 22 个“时刻”开始,每一个“时刻” 22 号节点都会“接受”一个来自 11 号节点的小球。

再比如说一个图 1→2,1→31 \to 2,1 \to 3,这个时候 11 号节点给出的球会在 22 号节点和 33 号节点之间“反复横跳”,并被“接受”。如果是图 1→2,1→3,2→31 \to 2,1 \to 3,2 \to 3,可以得到 33 号节点从第 22 个“时刻”开始,每奇数个“时刻”会“接受” 22 个小球,偶数个时刻不接受小球。

我的问题是,能否编写比较快速的程序,能够预测第 TT 时刻每个节点“接受”的小球数量?或者有没有数学方法可以得到答案?如果有这样的题目(不要类似,要一模一样),我也可以去看题解的。

2023/8/1 20:10
加载中...