esc to dismiss
x
Home / week-88 / 881

信息

题解

解法1: 拓扑排序 - 啰唆

  1. [a, b] 表示 a 比 b更有钱.

    • 最后求不比 i 钱少的中, 最安静的, 全局最有钱的答案对应其自身.
    • 记[a, b]为b -> a, 则找到哪个出度为0, 则对应为最有钱的.

    • 处理掉这个最有钱的后, 将b的出度减一,

    • 这时如果b的出度变为了0, 那么b就变为了此时最富的, 再重复处理

    • 处理的过程: 看是不是之前有比它更有钱的,

    • 如果有, 从中找出最安静的那个

      • 记得非直接连接的, 需要利用已有的答案
    • 如果没有, 那它自身就是 
pub fn loud_and_rich(richer: Vec<Vec<i32>>, quiet: Vec<i32>) -> Vec<i32> {
    use std::collections::{HashMap, HashSet, VecDeque};

    let mut out = vec![0; quiet.len()];
    let mut oout = HashMap::new();
    let mut iin = HashMap::new();
    for rich in richer {
        let (to, from) = (rich[0] as usize, rich[1] as usize);
        out[from] += 1;
        iin.entry(to).or_insert(HashSet::new()).insert(from);
        oout.entry(from).or_insert(HashSet::new()).insert(to);
    }

    let mut queue = VecDeque::new();
    for (idx, &cnt) in out.iter().enumerate() {
        if cnt == 0 {
            queue.push_back(idx); // 这点起始就是最富
        }
    }

    let mut ans = vec![0; quiet.len()];
    while !queue.is_empty() {
        let sz = queue.len();
        for _ in 0..sz {
            let rich = queue.pop_front().unwrap();
            // rich 是当前最富的, 但不一定是全局最富的,
            // 因此检查其指向谁, 然后取下一个节点, 和其ans中的最安静的那个
            let (mut most, mut qu) = (rich, quiet[rich]);

            for &node in oout.get(&rich).unwrap_or(&HashSet::new()) {
                if quiet[node] < qu {
                    most = node;
                    qu = quiet[node];
                }
                let node_ans = ans[node] as usize;
                if quiet[node_ans] < qu {
                    most = node_ans;
                    qu = quiet[node_ans];
                }
            }
            ans[rich] = most as i32;

            // 将指向 rich 的节点, 出度都减1
            for &node in iin.get(&rich).unwrap_or(&HashSet::new()) {
                out[node] -= 1;
                if out[node] == 0 {
                    queue.push_back(node); // 出度为0, 下一轮的最富
                }
            }
        }
    }
    ans
}

解法2: 拓扑排序 - 精简

Info
  1. 通过 graph 记录谁比 i 更穷(直接)
  2. 穷的那个, 记录下有几个比自己更富有, 即入度
  3. 如果入度为0, 则这个节点为"最"富有的
  4. 将入度为0的节点存入节点, 逐个处理
  5. 全局最富有的节点, 其答案就是其自身
  6. 计算出相对富有后, 更新比它穷的节点, 可选项有:
  7. 穷节点自身
  8. 富节点的答案
  9. 但相对穷的节点, 可能并不止一个相对富的节点,
  10. 其入度减1, 为0之后升级为"最"富有的节点, 存入队列 
pub fn loud_and_rich(richer: Vec<Vec<i32>>, quiet: Vec<i32>) -> Vec<i32> {
    use std::collections::VecDeque;

    let mut graph = vec![vec![]; quiet.len()];
    let mut in_deg = vec![0; quiet.len()];
    for r in richer {
        let (rich, poor) = (r[0] as usize, r[1] as usize);
        graph[rich].push(poor); // 记录谁比它穷
        in_deg[poor] += 1; // 入度为0的, 为最富的
    }

    let mut ans = (0..quiet.len() as i32).collect::<Vec<i32>>(); // 先用自身填位
    let mut queue = VecDeque::new();
    for (idx, &ii) in in_deg.iter().enumerate() {
        if ii == 0 {
            queue.push_back(idx);
        }
    }

    while !queue.is_empty() {
        let rich = queue.pop_front().unwrap();
        // 先计算更富有的, 全局最富有的, 其最终答案就是它自身
        let ans_rich = ans[rich] as usize;
        for &poor in graph.get(rich).unwrap() {
            // 计算出富有的之后, 更新比它穷的
            let ans_poor = ans[poor] as usize;
            if quiet[ans_rich] < quiet[ans_poor] {
                ans[poor] = ans_rich as i32;
            }
            // 从这个 rich 到 这个 poor 已经检查过了
            // 后面不用在检查了, 因此对poor来说, 入度减1
            in_deg[poor] -= 1;
            if in_deg[poor] == 0 {
                // 这时poor已经没有入度, 因此升级为最富有的
                queue.push_back(poor);
            }
        }
    }
    ans
}

解法3: DFS

Info
  1. 通过 graph 记录谁比 i 更富有(直接)
  2. 通过DFS逐层深入, 直到最富有
  3. 全局最富有, 则最终答案就是它自己
  4. 相对 i 富有的得到答案后, 更新 i 对应的答案, 可能的答案有
  5. 自身 i
  6. 相对 i 富有的节点的答案
  7. 由于相对 i 富有(直接)的节点可能不止一个, 因此需要都检查一下 
pub fn loud_and_rich(richer: Vec<Vec<i32>>, quiet: Vec<i32>) -> Vec<i32> {
    let mut graph = vec![vec![]; quiet.len()];
    for r in richer {
        let (to, from) = (r[0] as usize, r[1] as usize);
        graph[from].push(to); // to 是 比 from 富有的
    }

    fn dfs(ans: &mut Vec<i32>, graph: &Vec<Vec<usize>>, quiet: &Vec<i32>, x: usize) {
        if ans[x] != -1 {
            // 已经判出结果的, 不用重复判
            // 不论结果是啥, 因为dfs后有更新的逻辑
            // 所以只要有结果, 那就是最终答案
            return;
        }
        ans[x] = x as i32; // 用自身填位先
        for &y in graph.get(x).unwrap() {
            dfs(ans, graph, quiet, y);
            // 比x富有的答案
            let ans_x = ans[x] as usize;
            // 比x富有的的y的最终答案,
            // 由于是先执行的dfs, 因此这里已经拿到相对富有的y的最终答案
            let ans_y = ans[y] as usize;
            if quiet[ans_y] < quiet[ans_x] {
                ans[x] = ans[y]; // 比x富有的y, 有比当前结果更安静的
            }
        }
    }

    let mut ans = vec![-1; quiet.len()];
    for i in 0..quiet.len() {
        // 都尝试一遍, 因为不定哪个最富, 哪个最穷
        dfs(&mut ans, &graph, &quiet, i);
    }
    ans
}

Backlinks

Tags

x