Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ARC076-B Built?】クラスカル法の理解「どうせ選ばれない枝には興味がない」

D - Built?

問題

平面上にN個の点がある。点(a,b)と点(c,d)を結ぶ時、コストmin(|a-c|,|b-d|)がかかる。いくつかの点を結んで、N個の点を連結させたい。その時の合計コストはいくらか?

方針

最小全域木のコストを調べればよい。(閉路があるなら、枝を削除してもよく、木には出来るから。そしてそのうちで最小のものを選択すればよいから)Vが大きいのでプリム法O(V2)は使用出来ない。クラスカル法ならO(E logV)なのでEを減らせば使えそう。

見た目には、N個の点は全部結ばれているのでE=V2に見えるが、クラスカル法の動作を考えればVに減らせる。

例えば点をX方向でソートする。仮に、その時、隣接しない点をつなぐ意味はない。なぜならば、クラスカル法を実行すると、そのコストの枝を選択する時にはすでに、中間にある点が全部繋がっているからである。

従って、隣接する点だけを繋げばよい。

Y方向についても同様。

実装

fn solve() {
    input!{
        N:usize,
        P:[(u64,u64);N],
    }
    let mut es = vec![];

    let mut ps = vec![];
    for i in 0..N {
        let p=P[i];
        ps.push((i,p.0,p.1));
    }
    // xでソート
    ps.sort_by_key(|&p| p.1);
    for i in 0..N-1 {
        let p0 = ps[i];
        let p1 = ps[i+1];
        let dist=p1.1-p0.1;
        es.push(Edge {u:p0.0, v:p1.0, cost:dist});
    }

    // yでソート
    ps.sort_by_key(|&p| p.2);
    for i in 0..N-1 {
        let p0 = ps[i];
        let p1 = ps[i+1];
        let dist=p1.2-p0.2;
        es.push(Edge {u:p0.0, v:p1.0, cost:dist});
    }

    let cost=kraskal(N, &mut es);
    println!("{}",cost);
}

考察

これは、直接ではないが、上位K個系ともいえる。X方向での隣接した上位V個と、Y方向での隣接した上位V個によって作られるグラフしか必要ないため。

www.rustforbeginners.com