分享到plurk 分享到twitter 分享到facebook

版本 2851070512c131e9b68b46c4da23bd8d8f1fdd5f

contest/acm/POJ/2771

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 也可用匈牙利~