読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2168 Luigi's Tavern

マッチングかー,フローっぽいなあ,どう見てもフローじゃん
みたいな感じだった

解法

パーティーを沢山作りたいので,各パーティーに役職はそれぞれ高々一人でいいことが分かります.
それで,人を頂点,友好関係を辺として張ってみると各頂点を高々一回ずつ使ってマッチングを沢山作ってくださいみたいな問題に見えてくると思います.
とりあえず簡単化のために,各パーティは必ず4つの役職全てを含む場合を考えてみましょう.
各頂点を高々一回というのは,頂点を入り口用と出口用の頂点二つに分割して,入り口と出口を流量1の辺で繋げば実現できます.
これでこのケースはグラフを構築してフローを流すだけで解けることが分かりました.

では各役職が欠けてもいい場合について考察してみましょう.
ある役職が欠けてる場合は,フローを流すときその役職をスキップしてフローを流すことができると考えることができます.
スキップする回数も制限がありますが,スキップするために使う頂点をその役職のダミーの人であると考えると,
ダミーの人がそれぞれNW,NC,NM人いると考えることができます.
そしたら同様に入り口と出口を分けてその間に人数分の流量の辺を張るだけになります.

グラフの構築ですが,自分で番号を決めるのではなく,どの役職の何番目の人=何番目の頂点みたいに変数として保存して置き,sz++ のようにして自動で割り当てていくと比較的楽になると思います.