2022-11-28：给定两个数组 A 和 B，比如 A = { 0, 1, 1 } B = { 1, 2, 3 } A[0] = 0, B[0] = 1，表示 0 到 1 有双向道路 A[1] = 1, B[1]

2022-11-28
北京
本文字数：1394 字
阅读完需：约 5 分钟

2022-11-28：给定两个数组 A 和 B，比如 A = { 0, 1, 1 }B = { 1, 2, 3 }A[0] = 0, B[0] = 1，表示 0 到 1 有双向道路 A[1] = 1, B[1] = 2，表示 1 到 2 有双向道路 A[2] = 1, B[2] = 3，表示 1 到 3 有双向道路给定数字 N，编号从 0~N，所以一共 N+1 个节点题目输入一定保证所有节点都联通，并且一定没有环默认办公室是 0 节点，其他 1~N 节点上，每个节点上都有一个居民每天所有居民都去往 0 节点上班所有的居民都有一辆 5 座的车，也都乐意和别人一起坐车车不管负重是多少，只要走过一条路，就耗费 1 的汽油比如 A、B、C 的居民，开着自己的车来到 D 居民的位置，一共耗费 3 的汽油 D 居民和 E 居民之间，假设有一条路那么 D 居民可以接上 A、B、C，4 个人可以用一辆车，去往 E 的话，就再耗费 1 的汽油。求所有居民去办公室的路上，最少耗费多少汽油。来自微软。

答案 2022-11-28：

dfn 序。

代码用 rust 编写。代码如下：

use std::iter::repeat;
fn main() {    let mut a1 = vec![0, 1, 1];    let mut b1 = vec![1, 2, 3];    let n1 = 3;    println!("ans = {}", min_fuel(&mut a1, &mut b1, n1));
    let mut a2 = vec![1, 1, 1, 9, 9, 9, 9, 7, 8];    let mut b2 = vec![2, 0, 3, 1, 6, 5, 4, 0, 0];    let n2 = 9;    println!("ans = {}", min_fuel(&mut a2, &mut b2, n2));}
static mut CNT: i32 = 0;
fn min_fuel(a: &mut Vec<i32>, b: &mut Vec<i32>, n: i32) -> i32 {    // 先建图    let mut graph: Vec<Vec<i32>> = vec![];    for _i in 0..=n {        graph.push(vec![]);    }    for i in 0..a.len() {        graph[a[i] as usize].push(b[i]);        graph[b[i] as usize].push(a[i]);    }    // 建图完毕    // 根据题目描述，办公室一定是0号点    // 所有员工一定是往0号点汇聚
    // a 号，dfn[a] == 0 没遍历过！    // dfn[a] != 0 遍历过！    let mut dfn: Vec<i32> = repeat(0).take((n + 1) as usize).collect();    // a为头的树，一共有10个节点    // size[a] = 0    // size[a] = 10    let mut size: Vec<i32> = repeat(0).take((n + 1) as usize).collect();    // 所有居民要汇总吗？    // a为头的树，所有的居民是要向a来汇聚    // cost[a] : 所有的居民要向a来汇聚，总油量的耗费    let mut cost: Vec<i32> = repeat(0).take((n + 1) as usize).collect();    unsafe { CNT = 0 };    dfs(&mut graph, 0, &mut dfn, &mut size, &mut cost);    return cost[0];}
// 图 ： graph// 当前的头，原来的编号，不是dfn序号！ : cur// 从cur开始，请遍历// 遍历完成后，请把dfn[cur]填好！size[cur]填好！cost[cur]填好fn dfs(    graph: &mut Vec<Vec<i32>>,    cur: i32,    dfn: &mut Vec<i32>,    size: &mut Vec<i32>,    cost: &mut Vec<i32>,) {    unsafe {        CNT += 1;    }    dfn[cur as usize] = unsafe { CNT };    size[cur as usize] = 1;    for next in graph[cur as usize].clone().iter() {        if dfn[*next as usize] == 0 {            dfs(graph, *next, dfn, size, cost);            size[cur as usize] += size[*next as usize];            cost[cur as usize] += cost[*next as usize];            cost[cur as usize] += (size[*next as usize] + 4) / 5;        }    }}