Description:
ある保守的な先生が生徒を旅行に連れて行くのだが、旅行中にカップルが出来るといった事態を避けたいと思っている。
以下の4つの内のどれかを満たすなら、その二人はくっつく可能性は少ないだろう。
1. 身長差が40cm超
2. 同性
3. 好きな音楽のスタイルが異なる
4. 同じスポーツが好き
出来るだけ多くの生徒を旅行に連れて行きたいが、くっつく可能性の有る二人を両方連れて行くことは出来ない。
N人(1<=N<=500)の生徒の身長、性別、好きな音楽、スポーツが与えられた時、最大で何人まで連れて行くことが可能か計算せよ。
Answer:
二部グラフの最大安定集合
くっつく男女間で枝が張られた二部グラフを考える。
すると、人数 - このグラフの最大マッチングが答えになる。
証明)
srcから男全員に枝、男からくっつく可能性の有る女全員に枝、女全員からsinkに枝を張ったグラフを考える。
そして、このグラフからsrc-男間の枝、女-sink間の枝を何本か取り除き、取り除いた枝に関与する生徒は連れて行かなかった、枝が残っている生徒は連れて行ったと考えると、
グラフにフローが存在する == 連れて行った生徒でカップルが存在 と考える事が出来る。
男A-女Bの枝を取り除くより、src-男Aの枝を取り除いた方がフローを小さくする上で適している為、枝を取った後のグラフが、生徒を最大まで連れて行った状態だとすると、このグラフははじめのグラフの最小カットとなっている。
最大フロー = 最小カットの定理より、 どうしても連れて行くことが出来ない最小の人数は、はじめのグラフの最大フローに等しい。
はじめのグラフの最大フロー = 男女間二部グラフの最大マッチング である為、求める答えは、人数 - 二部グラフの最大マッチングの大きさ。
Source: