anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM 最小費用流 二部マッチング 辞書順最小 問題 Editorial 問題 クラスが複数個ある( 「クラス複数個中からxつ以上のクラスを取る必要がある」という要求が複数( 全ての要求を満たしたい。 ただし、クラスは一つの要求にしか使うことができない。 また、既にとっているクラスが複数個与えられて、それはどれかの要求に使うことが出来る。 このとき、新たに取らなければいけないクラスの数を最小化し、取るクラスを辞書順最小化せよ。 どうやっても要求を満たせない場合は"0"を返せ 解答 「xつ」という数値での制約は最小費用流かな、と思い考える。 以下のようなフローネットワークを考えた(赤は容量, 青は費用) 後から思うと、最小費用流にしてはコスト… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20121210%2F1355066524" title="SRM 200 DIV1 Hard Graduation - antaの競技プログラミング練習日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/a/anta1/20121210/20121210000401.jpg Hatena Blog https://hatena.blog 2012-12-10 00:22:04 rich https://anta1.hatenadiary.org/entry/20121210/1355066524 1.0 100%