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

• 洛谷 P2700逐个击破 题解 C++
• • 题目大意
  • 思路
  • • 贪心证明
  • 详细做法
  • 代码
  • 样例

给定N个点的一棵树以及N-1条无向边和该边的销毁代价w，要求其中K个点互相不能到达所花费的最小代价
K5，1<=w<=10⁶

我们先想一下可不可以删边，想不出什么思路？好像很不可做的样子。正难则反，我们是不是可以选择尽可能选择边使得K个被占领的点互相不连通且边权和最大(最大不连通边权和)，那么删去边的边权之和就是总边权和-最大的不连通边权和。那我们是不是可以贪心一下，把边权和从大到小排个序，如果连上这条边后K个点不能互相到达，那么就选择这条边

相信肯定有人抬杠有疑问，觉得贪心不一定最优，那么我们试图证明感性理解一下
两条路径如果没有公共节点，那肯定可以两条路径都选，如果有一条被占领点可以到达，那我另一条路径也可以只不选一个，可最大的边权又选了，所以必定可以先选大的

我们连边的时候怎么考虑这条边会不会让K个点相互到达呢，答案是——把它存下来，每次发现加入的边中若有一点被占领，那么其能到达的点都可以算作被占领，也就是DFS一下，经过的点标记一下，然后如果DFS中遍历到已经被占领的点就不要再重复遍历了，因为之前肯定已经被遍历过了

#include
using namespace std;
struct edge {
	int u,v,w;
}a[100005];//存边
long long n,k,sum,maximum;
bool occupy[100005];//表示每个点是否被占领，true为占领，false为未占领
vector fa[100005];//记录已选择边的每个点的父亲
vector son[100005];//记录已选择边的每个点的儿子
bool cmp(edge a1,edge a2){//sort函数中的结构体排序
	if(a1.w>a2.w)return true;
	else return false;
}
void DFS(int now,int last){
	if(occupy[now])return ;//如果这个点已经被占领，那之前肯定跟这个点连的边肯定都遍历过了，就不用再次遍历了
	occupy[now] = true;
	for(int i = 0;i>n>>k;
	for(int i = 0;i>x;
		occupy[x] = true;
	}
	for(int i = 0;i>a[i].u>>a[i].v>>a[i].w;
		sum+=a[i].w;
	}
	sort(a,a+n-1,cmp);//边权从大到小排序
	for(int i = 0;i 
样例 
输入样例1：
 
 
 
13 5
 1 2 3 6 7
 0 1 5
 0 2 2
 1 3 7
 1 4 2
 1 5 1
 1 6 2
 5 7 4
 5 8 9
 8 10 8
 2 9 9
 9 12 3
 9 11 11
 
 
输出样例1：12