【题解】CCPC-final 2019 Problem B - Infimum of Paths

60 阅读 0 评论 40 点赞

我是靠谱客的博主拼搏白云，最近开发中收集的这篇文章主要介绍【题解】CCPC-final 2019 Problem B - Infimum of Paths，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题意
求有向图0道1的字典序最小路径（注意，这里转化成小数值，所以和路径长度毫无关系，末尾可以接无数个0）

观察：
肯定会有无限循环的情况，但是只会在一个最优的环上走
这道题首先要做两个事情
删除不能到1的点
把1加上0的自环，这样可以把无限和有限放在一起处理

有三种方法。其中两种是题解的

方法1

正着走，贪心的思想，每次走最优的路径。更新合法的点集（注意这里需要去重，否则会指数级增长）。走3n步
前n步一定走到一个环上（包括1的自环），于是在[n,3n - 1]找最小循环节
这种做法思路是最直白的。也非常好写
code

方法2

用基数排序的思想把长度为n的路径排序。基于对n - 1的顺序
给每个点一个rank，表示第i轮，它出发的最优路径（长度为i）的排名
第i + 1轮时，找到它出发的(最小边,最小rank点)（这是二元组的排序）。
复原路径时把环复原出来
处理无限循环小数等差数列求和即可（我没有学过小学数学）
code

方法3

思路和方法2基本相同，但是是我在看题解前独立想出来的。所以也写了一下
从1开始倒着更新，想bfs一样。rank记录当前每个点到1的最优路径的排名
按照边权为第一个关键字，排名为第二关键字去更新
这样实现起来方便，也不需要去掉不能到1的点，for的时候非常直白
code

总结

这道题的模型非常经典，求最小字典序路径，在图论中融入了字符串比较的思想。后两种方法主要就是应用基数排序的思想。我是受这道题的启发，就直接往bfs方向想了。
第一种方法则没有用什么字符串的思想，就直接贪心，保证步步都合法（可以走到终点）
想清楚每个模块，然后再稍微注意一下实现的细节（如何最简单），并不难写。