Description
给定一个带边权有向图。现在从点 \(1\) 开始走,走的过程中可以无代价回溯任意多步,求在经过最多点的情况下(重复的点算一次),最小边权和是多少。
Solution
先从点 \(1\) BFS,能走到的点就是第一小问答案。根据回溯条件,在最优答案中,每条边至多走一次(考虑走两次的话,一定有一次是不必要的,可以通过调整回溯策略来消去)。以及走过的边不会形成环,否则可以通过在形成环的那一步通过回溯操作到达相同的点,且没有花费。所以所有所经过的路径的集合构成一棵外向树。于是问题就转换为了,求原图的一棵以点 \(1\) 为根的外向最小生成树。
和无向图的最小生成树求法有些许差别,该外向最小生成树需要保证除根以外的每个点都至少有一条入边,即有父亲。所以考虑用堆优化的 Prim ,从 \(1\) 开始扩展,每次新加入一个点,就把该点所有出边加到堆里面,每次取最小的边加入生成树,复杂度 \(O(n\log m)\)。
标签:最小,生成,外向,回溯,滑雪,SCOI2012 From: https://www.cnblogs.com/wwlwQWQ/p/17852024.html