library_checker/graph/
minimum_spanning_tree.rs1use competitive::prelude::*;
2use competitive::{algorithm::SliceSortExt, graph::EdgeListGraphScanner};
3
4#[verify::library_checker("minimum_spanning_tree")]
5pub fn minimum_spanning_tree(reader: impl Read, writer: impl Write) {
6 prepare_io!(reader, writer);
7 sc!(n, m, (graph, w): @EdgeListGraphScanner::<usize, u32>::new(n, m));
8 let mut edges: Vec<_> = (0..m).map(|eid| (w[eid], eid as u32)).collect();
9 edges.radix_sort_by_key(|&(weight, _)| weight);
10 let span = graph
11 .minimum_spanning_tree_from_sorted_edges(edges.into_iter().map(|(_, eid)| eid as usize));
12 let ans = (0..m).filter(|&eid| span[eid]);
13 let total: u64 = ans.clone().map(|eid| u64::from(w[eid])).sum();
14 pp!(total; @it ans);
15}