Hackers’ Crackdown (UVa 11825)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2925

問題

ある会社のネットワーク上にはコンピュータとサービスがN個あり、各サービスは全てのコンピュータで動いている。ハッカーがいてその会社のサービスを止めたい。ハッカーは各コンピュータに一度ずつ攻撃を加えることができ、そのコンピュータとそのコンピュータに直接つながっているコンピュータ上で動く一つのサービスを停止させることが出来る。ネットワーク上でそのサービスを提供するコンピュータがいなくなった場合にそのサービスは完全に停止したことになる。最大何個のサービスを完全に停止させることが出来るか。
1<=N<=16

解法

ビットDP。