2023-03-20：给定一个无向图，保证所有节点连成一棵树，没有环，
给定一个正数n为节点数，所以节点编号为0~n-1，那么就一定有n-1条边，
每条边形式为{a, b, w}，意思是a和b之间的无向边，权值为w，
要求：给定一个正数k，表示在挑选之后，每个点相连的边，数量都不能超过k，
注意：是每个点的连接数量，都不超过k！不是总连接数量不能超过k！
你可以随意挑选边留下，剩下的边删掉，但是要满足上面的要求。
返回不违反要求的情况下，你挑选边所能达到的最大权值累加和。
来自Lucid Air。
答案2023-03-20：
1.算法分析
为了解决此问题，我们可以使用搜索和动态规划技术进行优化，下面将详细介绍两种算法的实现方法。
1.1.暴力搜索
首先，我们可以用暴力搜索来解决这个问题。具体地，我们从第一条边开始遍历，对于每条边，有两种选择：选择它或不选择它。如果选择当前边，则需要检查所有与该边相邻的点的度数是否小于等于k；如果不是，则说明该方案不符合条件，需要跳过。否则，递归考虑下一条边。最终，我们得到所有符合要求的方案，计算它们的总权值，取其中最大值即可。
虽然暴力搜索很容易理解，但时间复杂度为 O(2^n)，显然无法处理大规模数据。
下面是 Rust 实现的代码：
// 暴力方法
// 为了验证
fn max_sum1(n: i32, k: i32, edges: &Vec<Vec<i32>>) -> i32 {
process(edges, 0, &mut vec![false; edges.len()], n, k)
}
// 递归函数，尝试选择或不选择边，返回最大权值和
fn process(edges: &Vec<Vec<i32>>, i: usize, pick: &mut Vec<bool>, n: i32, k: i32) -> i32 {
// 如果已经枚举完所有的边
if i == edges.len() {
// 统计每个点的度数，并计算当前选中边的权值和
let mut cnt = vec![0; n as usize];
let mut ans = 0;
for j in 0..edges.len() {
if pick[j] {
cnt[edges[j][0] as usize] += 1;
cnt[edges[j][1] as usize] += 1;
ans += edges[j][2];
}
}
// 判断每个点的度数是否小于等于k，如果不是则返回-1
for j in 0..n as usize {
if cnt[j] > k {
return -1;
}
}
// 返回当前选中边的权值和
return ans;
} else {
// 尝试选择当前边
pick[i] = true;
let p1 = process(edges, i + 1, pick, n, k);
// 不选择当前边
pick[i] = false;
let p2 = process(edges, i + 1, pick, n, k);
// 返回两种情况的最大值
return p1.max(p2);
}
}
1.2.优化的深度优先搜索
为了提高效率，我们需要对暴力搜索进行优化。我们可以利用记忆化搜索来避免重复计算，并将问题拆分为两个状态，分别表示当前节点选择和不选择的最大权值和。具体地，我们从叶子节点开始向上递推，并维护一个辅助数组，记录与当前节点相邻的子节点选择当前节点时，与不选择当前节点时的权值差。然后，根据这个数组，对DP数组中的两个状态进行更新。最后，返回根节点的“不选择”状态即可。
下面是具体的实现步骤：
（1）首先，定义两个全局变量 DP 和 HELP。DP[i][0] 表示不选择第 i 个节点时的最大权值和，DP[i][1] 表示选择第 i 个节点时的最大权值和。HELP 数组用于辅助计算，记录与当前节点相邻的子节点选择当前节点时，与不选择当前节点时的权值差。
（2）接下来，我们构造邻接表来表示输入的树。对于每个节点，我们存储一个包含其相邻节点的列表，同时也存储每条边的权值。例如，对于边 (i, j) 来说，我们将 (j,c) 添加到第 i 个节点的相邻节点列表中，将 (i,c) 添加到第 j 个节点的相邻节点列表中，其中 c 表示边的权值。
（3）然后，我们调用 dfs 函数，从根节点开始遍历整棵树。dfs 函数接受一个参数 i，表示当前节点的编号，以及一个参数 parent，表示当前节点的父节点。初始时，我们将 DP[i][1] 初始化为该节点与其相邻节点的权值之和，DP[i][0] 初始化为 0。
（4）接下来，我们遍历当前节点的相邻节点 j，并判断当前节点是否为其父节点。如果是，则跳过；否则，递归调用 dfs 函数处理子节点 j。
（5）在处理完子节点 j 后，我们需要更新 DP 和 HELP 数组。具体地，我们定义变量 sum 表示当前节点选择时的最大权值和，diff 表示当前节点不选择时的最大权值和。然后，我们遍历当前节点的相邻节点，并累加它们相对于当前节点选中或不选中的权值差到 HELP 数组中。最后，根据 HELP 数组，我们更新当前节点的 DP 值。更新方式如下：
如果当前节点选择，则有 DP[i][1] = sum + HELP[j][1]，DP[i][0] = max(DP[i][0], sum + HELP[j][0])；
如果当前节点不选择，则有 DP[i][0] = diff + HELP[j][1]，DP[i][1] = max(DP[i][1], diff + HELP[j][0])。
注意，在更新 DP[i][1] 时，我们需要加上当前节点与子节点 j 之间的边的权值。最后，我们返回 DP[root][0] 即可得到答案。
（6）最后，我们可以在 main 函数中读入输入数据，调用 dfs 函数求解问题，并输出结果。
使用优化的深度优先搜索算法，时间复杂度为 O(n)，空间复杂度为 O(n)。
下面是 Rust 实现的代码：
// 定义两个全局变量
static mut DP: [[i32; 2]; 100001] = [[0; 2]; 100001];
static mut HELP: [i32; 100001] = [0; 100001];
// 主函数，返回最大权值和
pub fn max_sum2(n: i32, k: i32, edges: &Vec<Vec<i32>>) -> i32 {
// 构造邻接表
let mut graph = vec![vec![]; n as usize];
for edge in edges {
let a = edge[0];
let b = edge[1];
let c = edge[2];
graph[a as usize].push(vec![b, c]);
graph[b as usize].push(vec![a, c]);
}
// 初始化DP数组为-1，并递归调用dfs函数求解最大权值和
unsafe {
for i in 0..n as usize {
DP[i][0] = -1;
DP[i][1] = -1;
}
dfs(0, -1, k, &graph);
DP[0][0]
}
}
// 深度优先搜索函数，计算以当前点为根节点的子树内选择一些边能够得到的最大权值和
pub fn dfs(cur: usize, father: i32, k: i32, graph: &Vec<Vec<Vec<i32>>>) {
let edges = &graph[cur];
let mut ans0 = 0; // 不选当前节点时的最大权值和
let mut ans1 = 0; // 选当前节点时的最大权值和
let mut m = 0; // HELP数组中实际存储的元素个数
unsafe {
for i in 0..edges.len() {
// 遍历当前节点的所有邻居节点
let next = edges[i][0] as usize;
if next != father as usize {
// 如果邻居不是父节点，则递归调用dfs函数
dfs(next, cur as i32, k, graph);
}
}
for i in 0..edges.len() {
// 再次遍历邻居节点，统计ans0、ans1以及HELP数组
let next = edges[i][0] as usize;
let weight = edges[i][1];
if next != father as usize {
ans0 += DP[next][0];
ans1 += DP[next][0];
if DP[next][0] < DP[next][1] + weight {
HELP[m] = DP[next][1] + weight - DP[next][0];
m += 1;
}
}
}
HELP[..m].sort_unstable_by(|a, b| b.cmp(a)); // 对HELP数组进行排序
for (i, help_i) in HELP[..m].iter().enumerate() {
// 根据HELP数组更新ans0、ans1
let cnt = i as i32 + 1;
if cnt <= k - 1 {
ans0 += help_i;
ans1 += help_i;
}
if cnt == k {
ans0 += help_i;
}
}
DP[cur][0] = ans0; // 将结果保存到DP数组中
DP[cur][1] = ans1;
}
}
2.两种算法的对数器
2.1.我们首先定义三个变量：n、v和test_times。其中，n表示节点数，v表示每个节点可能的最大权值和，test_times表示测试次数。
let n = 16;
let v = 50;
let test_times = 2000;
2.2.接着，我们使用for循环进行多次测试，每次测试随机生成一个节点数n_i32和要选取的节点数k，并使用random_edges函数生成一棵随机树的边列表。
for _ in 0..test_times {
let n_i32 = rand::thread_rng().gen_range(1, n + 1);
let k = rand::thread_rng().gen_range(1, n_i32 + 1);
let edges = random_edges(n_i32, v); // 生成随机的边
2.3.然后，我们调用max_sum1函数来计算最大权值和，并将其赋值给变量ans1。
let ans1 = max_sum1(n_i32, k, &edges);
2.4.我们接着调用优化后的解法max_sum2函数来计算最大权值和，并将其赋值给变量ans2。
let ans2 = max_sum2(n_i32, k, &edges);
2.5. 最后，我们将ans1与ans2进行比较，如果两者不相等，则说明代码存在错误，我们输出一条错误消息并退出程序。否则，我们继续进行下一轮循环。
if ans1 != ans2 {
println!("出错了!");
return;
}
2.6.在所有测试结束后，我们输出一条测试结束的消息。
println!("测试结束");
3.rust的完整代码
use rand::Rng;
// 为了测试
fn main() {
let n = 16;
let v = 50;
let test_times = 2000;
println!("测试开始");
for _ in 0..test_times {
let n_i32 = rand::thread_rng().gen_range(1, n + 1);
let k = rand::thread_rng().gen_range(1, n_i32 + 1);
let edges = random_edges(n_i32, v); // 生成随机的边
let ans1 = max_sum1(n_i32, k, &edges); // 调用暴力解法求解最大权值和
let ans2 = max_sum2(n_i32, k, &edges); // 调用优化后的解法求解最大权值和
if ans1 != ans2 {
// 如果结果不相等，则说明出错了
println!("出错了!");
return;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn max_sum1(n: i32, k: i32, edges: &Vec<Vec<i32>>) -> i32 {
process(edges, 0, &mut vec![false; edges.len()], n, k)
}
// 递归函数，尝试选择或不选择边，返回最大权值和
fn process(edges: &Vec<Vec<i32>>, i: usize, pick: &mut Vec<bool>, n: i32, k: i32) -> i32 {
// 如果已经枚举完所有的边
if i == edges.len() {
// 统计每个点的度数，并计算当前选中边的权值和
let mut cnt = vec![0; n as usize];
let mut ans = 0;
for j in 0..edges.len() {
if pick[j] {
cnt[edges[j][0] as usize] += 1;
cnt[edges[j][1] as usize] += 1;
ans += edges[j][2];
}
}
// 判断每个点的度数是否小于等于k，如果不是则返回-1
for j in 0..n as usize {
if cnt[j] > k {
return -1;
}
}
// 返回当前选中边的权值和
return ans;
} else {
// 尝试选择当前边
pick[i] = true;
let p1 = process(edges, i + 1, pick, n, k);
// 不选择当前边
pick[i] = false;
let p2 = process(edges, i + 1, pick, n, k);
// 返回两种情况的最大值
return p1.max(p2);
}
}
// 定义两个全局变量
static mut DP: [[i32; 2]; 100001] = [[0; 2]; 100001];
static mut HELP: [i32; 100001] = [0; 100001];
// 主函数，返回最大权值和
pub fn max_sum2(n: i32, k: i32, edges: &Vec<Vec<i32>>) -> i32 {
// 构造邻接表
let mut graph = vec![vec![]; n as usize];
for edge in edges {
let a = edge[0];
let b = edge[1];
let c = edge[2];
graph[a as usize].push(vec![b, c]);
graph[b as usize].push(vec![a, c]);
}
// 初始化DP数组为-1，并递归调用dfs函数求解最大权值和
unsafe {
for i in 0..n as usize {
DP[i][0] = -1;
DP[i][1] = -1;
}
dfs(0, -1, k, &graph);
DP[0][0]
}
}
// 深度优先搜索函数，计算以当前点为根节点的子树内选择一些边能够得到的最大权值和
pub fn dfs(cur: usize, father: i32, k: i32, graph: &Vec<Vec<Vec<i32>>>) {
let edges = &graph[cur];
let mut ans0 = 0; // 不选当前节点时的最大权值和
let mut ans1 = 0; // 选当前节点时的最大权值和
let mut m = 0; // HELP数组中实际存储的元素个数
unsafe {
for i in 0..edges.len() {
// 遍历当前节点的所有邻居节点
let next = edges[i][0] as usize;
if next != father as usize {
// 如果邻居不是父节点，则递归调用dfs函数
dfs(next, cur as i32, k, graph);
}
}
for i in 0..edges.len() {
// 再次遍历邻居节点，统计ans0、ans1以及HELP数组
let next = edges[i][0] as usize;
let weight = edges[i][1];
if next != father as usize {
ans0 += DP[next][0];
ans1 += DP[next][0];
if DP[next][0] < DP[next][1] + weight {
HELP[m] = DP[next][1] + weight - DP[next][0];
m += 1;
}
}
}
HELP[..m].sort_unstable_by(|a, b| b.cmp(a)); // 对HELP数组进行排序
for (i, help_i) in HELP[..m].iter().enumerate() {
// 根据HELP数组更新ans0、ans1
let cnt = i as i32 + 1;
if cnt <= k - 1 {
ans0 += help_i;
ans1 += help_i;
}
if cnt == k {
ans0 += help_i;
}
}
DP[cur][0] = ans0; // 将结果保存到DP数组中
DP[cur][1] = ans1;
}
}
// 为了测试
// 生成随机边的函数，返回一个包含n-1条边的vector
fn random_edges(n: i32, v: i32) -> Vec<Vec<i32>> {
let mut order = vec![0; n as usize];
for i in 0..n {
order[i as usize] = i;
}
let mut edges = vec![vec![0; 3]; (n - 1) as usize];
let mut rng = rand::thread_rng(); // 初始化随机数生成器
let mut i = n - 1;
while i >= 0 {
order.swap(i as usize, rng.gen_range(0, i + 1) as usize); // 随机交换两个位置
i -= 1;
}
for i in 1..n {
edges[(i - 1) as usize][0] = order[i as usize];
edges[(i - 1) as usize][1] = order[rng.gen_range(0, i) as usize]; // 随机选择一条边
edges[(i - 1) as usize][2] = rng.gen_range(1, v + 1); // 随机生成其权值
}
edges
}
4.运行结果
如图所示，两种算法的运行结果是一致的，说明算法没有问题。
