/ 最近 .rdf 追記 編集 設定 本棚

脳log[20201121] AtCoder Regular Contest 108/C 問題 Keep Graph Connected



2020年11月21日 (土)

最終更新: 2020-11-22T08:26+0900

[AtCoder] AtCoder Regular Contest 108C 問題 Keep Graph Connected

コンテスト中に問題文は理解していたと思う。文は。問題まで理解していたかは知らない。

  1. 頂点対抗で辺の奪い合いをする。
  2. 各頂点は自身に繋がる辺からこれはと思うグループをひとつ選び、それら辺に共通する番号を名乗る。
  3. このときその頂点に直接繋がる他の頂点は同じ番号を名乗ることができなくなる。
  4. そうして全頂点がちょうどひとつの番号と辺(のグループ)を選び取ったとき、選ばれた辺で全体がひとつに繋がっていればそれが答え。

これを DFS で探索しようとした。だめな選択に早々に見切りをつけて手戻りを減らすために、選択肢の少ない頂点に優先して選ばせようとした。

あとで提出して確かめる。TLE になるならさらに考えないといけない。WA になるなら問題文を読み直さないといけない。


あ、選ばなくていい頂点もあるのか。木の根に相当する頂点。選ばれる辺の数は N-1 以上になるから必ずなにがしかの木+余分な辺になるわけだけど、それがどういう意味を持つのか。最後の頂点だけ選べなくてもいいってだけ? わからなくなってきた。