ABの二完。
No.1917 LCMST
解説AC。
一見手がかりのない問題だけど、最小全域木を作る方法は普通はクラスカル法かプリム法なわけなので、
・最小全域木を作る方法としてクラスカル法を用いよう、そのために、辺の候補を絞り込もう
と考えるのが重要。
そして、最小公倍数が問題になっているのだから、約数・倍数の関係を用いて絞り込むのだろうな、と考えれば（証明はともかく）解説の方法を思い付くことは可能そう。
難しいけど、多分こうだろうな、という考察を推し進めていけば思いつけない問題ではなかった。
0 件のコメント:
コメントを投稿