SRM447 Div1 500

とぷこだ 過去問

問題

Facebookでの「知ってるかもしれない人」featureの改善をする。
Facebookでは友達は対称であるが、推移性はない(AがBの友達ならばBはAの友達、でもAがBとCの友達だからといってBとCが友達とは限らない)。
今、n-friendという用語を定義する。2人が友達ならば1-friends。2人(Aさん,Bさん)が友達でなくて、あるCさんがAさんとn-friendsでBさんとCさんは友達ならばAとBさんは(n+1)-friendsとする。


「Distance Score」というものを導入する。AさんとBさんが友達ではなく、AさんとBさんが3-friendsでなくなるように頂点を削除する最小の数がこのScoreとする。なので、このスコアが高いということはAさんとBさんはお互いよく知っているとなる(多くの頂点を削除しないといけないから)


友達関係が与えられる。ある人1とある人2のDistance Scoreを返す。

考え方

n-friendsとは、AとBの距離がnであることと同じ。
そして、Distance Scoreの定義から2人の最短距離が3以上となるようにするため、「人1->点->人2」か「人1->点->点->人2」となっている点を削除すればいい。


これは最小点カバー問題で、「人1からの距離1の点」と「人1からの距離2の点」の2部グラフになる。2部グラフでは「最小点カバー」＝「最大マッチング」なので、2部グラフのマッチング数が答えになる。


最大流で解く場合は、

  • ワーシャルフロイドで全点対最短距離を求める
  • 距離が1の点群と距離が2の点群に頂点を分ける(それ以外の頂点はどうでもいい)
  • 人1、人2、距離1の頂点、距離2の頂点でできるグラフを作る
  • 人1から人2への最大流を求める(＝最大マッチングのサイズ)

反省

逆に考えて、「最小点カバー」な問題っぽかったら2部グラフぐらいしかありえなかったり。