版本 2851070512c131e9b68b46c4da23bd8d8f1fdd5f
Changes from beginning to 2851070512c131e9b68b46c4da23bd8d8f1fdd5f
---
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 也可用匈牙利~