洛谷P2700逐题解析C++题解

洛谷 P2700逐个击破 题解 C++

文章结构概述

• 洛谷 P2700逐个击破 题解 C++

  • • 题目概述

    • 解题思路

    • • 贪心策略的论证

    • 具体实施步骤

    • 程序实现

    • 示例演示

题目大意解析

对于一棵由N个节点构成的树结构，已知其包含N-1条无向边，每条边对应一个销毁成本w，现需确定摧毁若干条边使得其中K个节点彼此间无法相互抵达，求实现该目标所需的最低总成本。约束条件为K<N<105，且每条边的销毁代价满足1<=w<=106。

思路

首先考虑是否可以删除某些边，但暂时没有想到可行的思路，似乎这一操作存在较大难度。采用正难则反的策略，我们是否可以尝试选择边的方式，使得K个被占领的点之间无法相互连通，并且所选边的权重总和达到最大值（即最大不连通边权和）？这样，被删除边的权重总和就等于全部边的权重总和减去这个最大不连通边权和。那么是否可以通过一种贪心的方法来实现这一目标？即按照边权重从高到低的顺序依次处理每条边，若连接该边后K个点之间仍无法相互到达，则保留这条边。

贪心证明

或许有人会提出异议，认为采取贪心策略未必能获得最优解，因此我们尝试进行一种直观的论证。若两条路径之间不存在任何共通节点，则显然可以同时选择这两条路