---
title: POJ2771
toc: no
categories: 題解 POJ Minimum_Independent_Set Bipartite_Matching
...

網址
====

http://poj.org/problem?id=2771

題目概述
====

Frank N. Stein 教授是一個保守的high-school老師，他想從N個學生裡面挑選一些人，一起去參加遠足

但是他害怕會有人因此成為情侶，所以所挑選的學生彼此之間至少滿足下列一項:

 - 身高差超過40公分

 - 同性別

 - 喜歡的音樂種類是不同的 

 - 喜歡的運動是一樣的 (因為一樣的話，可能會支持不同球隊，因而打架) 

在挑選出來的這些人當中，兩兩之間至少需要滿足上列其中一項的情況下，問最多可以挑幾個人?

Technique details
=================

  - 測試資料數量**T**，T <= 100

  - 學生數量**N**，N <= 500

  - 音樂及運動種類的字串長度都不超過100個字元，沒有任何空白會夾雜其中

輸入格式
-----

測資的第一行會有一個**T**，代表測試資料；接著每筆測試資料的第一行，會有一個**N**，

代表學生人數；接下來**N**行，每行有4個項目，分別代表學生的:

身高(整數)，性別(M或F)，音樂種類(字串)，運動種類(字串)

輸出格式
------

輸出一個整數，代表最多可以選幾個人一起參加遠足。

解題思路
======

兩人間只要符合任何一種條件，代表兩人都可以選

換言之，如果兩人4種條件都不符合，那鐵定兩人中只能選一個

於是使用Minimum Independent Set想法 (By宜龍)

先將所有學生分成男女兩組，放在左邊跟右邊

男生跟男生，以及女生跟女生彼此同性別之間，一定都可以選

所以當成不同的set(不建邊)

針對男生跟女生之間，倆倆檢查是否4個條件都不符合

假設某一對男女4個條件都不符合，則建邊，代表兩人只能選一個

因為剛剛已經先把男女分開了，所以變成Bipartite Graph

建一個超級源點，連到所有男生的flow是1，

建一個超級匯點，所有女生到該點的flow是1，

針對所有建出的邊，flow可以是1或無限大(無所謂)

求出Maximum Bipartite Matching的個數K後

用總人數**N**減去K就是答案了

複雜度:

兩兩之間建邊，O(N^2)

Maximum Bipartite Matching，依照implement而不同

用EK的話是O(NE^2)，Dinic則是(EN^2)

總複雜度O(EN^2)或O(NE^2+N^2)

 - 註: Maximum Bipartite Matching 也可用匈牙利~