HH 去散步 (对偶图) P2151 [SDOI2009]
关键词：递推、图论、矩阵加速
P2151 [SDOI2009] HH 去散步 - 洛谷
题目描述
HH 有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时 HH 又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。
现在给你学校的地图 (假设每条路的长度都是一样的都是 1)，问长度为 t，从给定地点 A 走到给定地点 B 共有多少条符合条件的路径。
输入格式
第一行：五个整数 N , M 法 A , B 。其中 N" 表示学校里的路口的个数，M 表示学校里的路的条数，t 表示 HH 想要散步的距离，A 表示散步的出发点，而 B 则表示散步的终点。
接下来 M 行，每行一组\(A_{i}\) , \(B_{i}\) ，表示从路口\(A_{i}\)到路口\(B_{i}\)有一条路。数据保证\(A_{i}â B_{i}\)，但不保证任意两个路口之间至多只有一条路相连接。路口编号从 0 到\(N-1\)。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模 45989。
输出格式
一行，表示答案。
分析
1. 计数问题，不是搜索就是递推，数据范围大，用递推
2. 递推就列表达式：
\[F_{n}[i, j]: i \to j 走n步的方案数\]
\[F_{n}[i, j] = F_{n-1}[i, k] + F_{n-1}[k, j]\]
3. 优化递推式：
不满足不两次都是来回走的限制，考虑加维 (怎么加？限制边不能再走，就加一维表示从哪条边来)，而起点确定，可以把表达式优化成：
\[F_{n}[e, j] = \sum_{u \stackrel{pre}{\to} k \to j} F_{n-1}[pre, k]\]
\(F_{n}[e, j]\) 表示从边e 来，走 n 步，到达 j 的方案数
t 的范围非常大，必须考虑矩阵加速：发现表达式中，体现的是边转移关系，边转移，就是在边间连 “边”，对偶图
4. 如何建立对偶图？
观察表达式，发现边还需表述 “走过该边到达哪” 的信息， 要表述该信息，就需要有向边。
用 [i,j] 表示如下关系：
\(u \stackrel{i}{\to} k \stackrel{j}{\to} v\)- 有向边 i 可经过一个点到达有向边 j，走过有向边 j 就相当于抵达点 v
- r 矩阵表示答案，从起点走 n 步到达该边的方案数
(根据上文，到达一个边相当于到达该边指向的点)
- g 矩阵表示边之间的转移关系，\(g[i, j] = 1\)表述 i 可以转移到 j
（注：豆包提供格式整理）
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
