Skip to main content

__debug's Home Keep it simple, stupid

[Codeforces 806D] Perishable Roads

Description

给你一个 \(n\) 个点的无向完全图, 每条边有正边权. 对于一个生成有根树, 定义其权值为每个点到根的路径上的最小权值之和. 对于每个点, 求出以它为根的权值最小的生成树.

\(n \le 2000\)

Solution

观察 1: 一定存在一个最优方案是一条链

观察 2: 每个最优方案中至少包括一条权值最小的边

观察 3: 一定存在一个链的最优方案, 使得在根到权值最小的边这一段路径上, 除最后一条边外, 边权严格递减

为了方便, 不妨将所有边减去最小值, 那么最小的边权将会变为 \(0\), 也就是说我们只需要找到一条根到某条 \(0\) 的路径使得其权值最小即可.

如果答案一定满足边权严格递减, 那么直接求最短路即可. 不妨倒过来考虑, 那么最后一条边会贡献两次, 直接从每个点选一个权值最小的出边, 将这个边权乘 \(2\) 作为初始距离, 跑多源最短路即可.

时间复杂度 \(O(n^2)\).

Comments

Comments powered by Disqus