1 条题解
-
0Guest LV 0
-
0
乍看题目描述,觉得这是一个无向图论。细看数据规模发现这其实是棵树(普通树或基环树)。
根据题意可知,本题求的是对树的最小字典序遍历方案。
“小Y每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。”说明当访问某个节点时,必须把该节点的所有子节点都访问完毕,否则剩余的节点将无法访问。基于以上分析,我们可以采用贪心策略。
(1)当m=n-1时,这是一棵树,直接从编号最小的节点开始进行深搜;由于输入是无序的,需要对编号进行排序预处理以提高搜索效率(即改变搜索序)。
(2)当m=n时,这是一棵基环树。所谓的基环树是指**n个点n条边的连通图,可以发现只有一个环,并且删掉环上任意一个边可以变成一棵树。**
针对基环树,每次割掉一条边后暴搜树,记录最小字典序方案,然后输出最优方案。此情况时间复杂度为n×n=2.5e7,妥妥的!
去环: 正在枚举的边的两个端点与正准备搜的另一条边的两个重合的话就是存在环,避开这种情况即可。
知识延伸:
找环的算法:tarjan,请自行科普。
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 3
- 已通过
- 1
- 通过率
- 33%
- 上传者