ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Dinic法(最大流,最小カット)

AOJ 3058 - Ghost (RUPC2019 Day2 H)

問題 提出コード 解法 燃やす埋める問題です。 詳しくはこちらを。 始点と終点および各幽霊に対応する作り、から各幽霊、各幽霊からに辺をはります。 この際、から出てくる辺を左に向くパターン、へ向かう辺を右に向くパターンとすると、 今番目の幽霊が向い…

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

ARC085 E - MUL

問題 提出コード 解法 燃やす埋める問題の応用です。 燃やす埋める問題についてはこちらを参考にするといいかと思います。 最小カットを使って「燃やす埋める問題」を解く 今回は、燃やす→売る、埋める→売らない、というようにして帰着させます。 s,tという2…

AOJ 3047 - Shiritori

問題 提出コード 解法 ある文字が最後の1文字となるには、ある文字が先頭となっている単語をすべて使い切った上で、その文字が最後の文字となっている単語にいきつくことが必要になります。 a~zまでの文字をそれぞれ頂点としたグラフを考えます。すべての単…

ABC009 D - 浮気予防

D - 浮気予防 提出コード 最小カットの問題に初めて触れました。 まずは、女の子と高橋君を頂点、友人関係を辺としたグラフを作成します。 そして、頂点0からへ繋がるパスが存在しなくなるような辺の切り方を考えることになります。 ここで、複数のゴールが…