4180

原题链接：P4081 题意 给定一颗 \(n\) 个点 \(m\) 条边的树，求这棵树的严格次小生成树。 严格次小生成树指：边权和大于最小生成树，且边权和最小的生成树。 思路 首先可以用克鲁斯卡尔求出这棵树的最小生成树，然后考虑用类似于反悔贪心的思路来做。 对于每一条不在最小生成树中的边 \(u \ ......

如果有两条在最小生成树上的边被换掉了，那么原树会被分成三个连通块。 考虑新加的两条边，保留权值较小的那一条，这样还剩两个连通块。而删除的两条边至少有一条能连通这两个连通块，所以可以保留那条边。 并且新加的两条边中权值较大的那一条肯定大于等于我们保留的边，否则与最小生成树的前提不符。 这样就证明了删除 ......

# [BJWC2010] 严格次小生成树 ## 题目描述 小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： ......

P4180 [BJWC2010] 严格次小生成树 /* 建立一个最小生成树 维护最大值和严格次小值 然后直接查询就可以了 5 6 1 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 */ #include <bits/stdc++.h> using namespace std; ......