#P12652. [集训队互测2025day2]生命的循环
[集训队互测2025day2]生命的循环
题目描述
生命是一张由 个神经节点与 条神经构成的带权有向图,允许存在自环和重边。
第 条神经记为 ,表示一条从 指向 的有向边,长度为 。
数据保证:对于图中的任意一条简单回路,其包含的所有边权之和不超过某个定值 ,并且始终有 。
定义 表示在时刻 ,神经节点 是否处于兴奋状态。
兴奋会沿神经传导:对于一条神经 ,若节点 在时刻 兴奋,则会向 传递信号,使 在时刻 进入兴奋状态。
节点的兴奋状态不会自动保留到下一时刻。也就是说,某个节点在一个时刻进入兴奋状态后,会立刻沿所有出边继续传递信号;之后若没有其它信号在某个时刻到达该节点,则该节点在该时刻不兴奋。
如果存在边权和为 的简单回路,那么信号可能在同一个时刻沿该回路递归传播。此时可以把整条零权简单回路等效地看作一个节点;这种传播不会让兴奋状态自动延续到下一时刻。
初始时刻 ,只有 号节点受到刺激并进入兴奋状态。此后信号在整个网络中不断传播。
保证经过充分长的时间后, 号节点的兴奋状态会进入周期。请你求它的最小正周期 ,即最小的正整数 ,使得存在某个有限的非负整数 ,满足
。
由于答案可能非常大,只需输出 。
输入格式
第一行输入三个整数 :
- 表示神经节点数;
- 表示神经条数;
- 表示当前测试点所属的子任务编号。样例中 。
随后 行,每行三个整数 ,表示一条从 指向 、长度为 的神经。
type 仅用于标识子任务,解题时不需要依赖它计算答案。
输出格式
输出一行一个整数,表示最小周期 对 取模后的结果。
输入输出样例
输入
5 7 0
1 2 0
2 3 1
3 2 5
3 5 1
1 4 0
4 4 9
4 5 1
输出
18
数据范围
对于所有测试数据:
- ;
- ;
- ;
- ;
- 任意简单回路的边权和不超过 。
子任务
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 原图为 DAG,即不存在任何简单回路 | |
| 2 | 8 | , |
| 3 | 11 | 原图强连通 |
| 4 | 10 | 至少存在一条包含节点 的简单回路 |
| 5 | 19 | 所有简单回路的点集两两不相交,且这些简单回路的总长度两两互质 |
| 6 | 9 | 所有简单回路的点集两两不相交,且每条简单回路的总长度都是某个质数的正整数次幂 |
| 7 | 18 | |
| 8 | 24 | 无特殊限制 |