Problemsetting (UVa Live Archive Europe - Southeastern - 2010/2011 Bucharest (Romania))Comments

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4819

問題

プログラミングコンテストがN個、問題がM問ある。各コンテストでは使える問題とコンテストで使用する問題の数が決まっている。同じ問題は使わないという条件下で最大何個のコンテストが開催できるか？
1<=N<=15
0<=M<=50

解法

どのコンテストを開くかを決めれば、最大流を使ってそれが実際に実行可能かを判定することができる。なので全ての組み合わせに対してチェックすれば良い。しかし、これだと間に合わないので、現在見つかった答え以下のコンテストしか開かない場合と、そもそもコンテストで使う問題数の総和がMより大きい場合は無視する。そうすると枝刈りが恐ろしく効き一瞬で答えが出る。