2023-03-20:给定一个无向图,保证所有节点连成一棵树,没有环, 给定一个正数n为节点数,所以节点编号为0~n-1

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.运行结果

在这里插入图片描述

如图所示,两种算法的运行结果是一致的,说明算法没有问题。

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商