2026-10-05
matching.rs
fn try_assign(p: usize, can_do: &[Vec<usize>], seen: &mut [bool], owner: &mut [Option<usize>]) -> bool {
for &job in &can_do[p] {
if seen[job] {
continue;
}
seen[job] = true;
if owner[job].is_none_or(|q| try_assign(q, can_do, seen, owner)) {
owner[job] = Some(p);
return true;
}
}
false
}
fn main() {
let can_do = [vec![0, 1], vec![0]];
let mut owner = [None; 2];
let mut seen = [false; 2];
let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut seen, &mut owner)).count();
println!("{n}");
}
main は、人ごとにこなせる仕事の一覧 can_do から、別々の仕事を割り当てられる最大の人数を数えるつもりのコードです。can_do は、人0が仕事0と1、人1が仕事0だけで、引数も標準入力も使いません。いまは 1 が出ます。人0を仕事1に、人1を仕事0に割り当てられるので、本来は 2 が出るはずです。
Answer
Wrong
let mut seen = [false; 2];
let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut seen, &mut owner)).count();
seen は、1回の探索の中で尋ね済みの仕事に付ける印ですが、main で1回だけ作られ、2人分の探索で共有されています。人0の探索で仕事0を取ったときに付いた seen[0] は、そのまま残ります。
人1の探索は仕事0から始まりますが、seen[0] が true なので尋ね済みとして飛ばされます。持ち主の人0に仕事1へ移ってもらう道は試されないまま false が返り、数えられるのは人0だけの 1 です。
Right
let n = (0..2).filter(|&p| try_assign(p, &can_do, &mut [false; 2], &mut owner)).count();
人ごとに新しい [false; 2] を渡せば、印は1人分の探索の中でだけ効きます。同じ探索で同じ仕事を2度尋ねないという本来の役目は残り、人1の探索は仕事0の持ち主の人0に尋ねます。人0が仕事1へ移り、人1が仕事0を取って、2 になります1。
- 印を消すのは探索が成功したときだけにする、という高速化もあります。失敗した探索で付いた印は、割り当てが変わらない限り、同じ仕事を何度尋ねても失敗するという情報だからです。このコードの誤りは、人0の探索が成功して割り当てが変わった後も印を残したことです。