版本 a7885f9ded72a3a0932a3e4619bf68b924df195c
Changes from a7885f9ded72a3a0932a3e4619bf68b924df195c to current
---
title: [POJ] 2771 - Guardian of Decency
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 :sup:`2`)
Maximum Bipartite Matching，依照implement而不同
用EK的話是O(NE :sup:`2`)，Dinic則是(EN :sup:`2`)
總複雜度O(EN :sup:`2`)或O(NE :sup:`2`+N :sup:`2`)
- 註: Maximum Bipartite Matching 也可用匈牙利~
