|
doba |
|
グラフ理論っぽいですね。
４つの町は、Ｓ町から到達可能なグループと、 その町からＧ町に到達可能なグループの２組に分けられ、 その分け方が決まれば対応する通行不能パターンも決まる、と考えました。 S/ABG SA/BG SB/AG SAB/G で４通りです。 必ず２つのグループに分けられる話は、 もし両方のグループに含まれる町があれば ＳからＧへのルートができることになるので不可、 もしどちらのグループにも含まれない町があれば、 どちらにも含まれない町とどちらかのグループの境界にある道が復旧しても ＳからＧには行けないことになるから不可。 |
|
11月8日（木） 0:41:34
39980 |