想不到這道是若干年後被改難然後翻炒…
題意說給出N人，每人會對某幾個人有關係，問最多可以選多少人，使得這群人互相不會有關係。
如果把沒有關係的人連一條邊，題目正好就是求Maximum Clique。不過這道題給的不是這條邊，而是赤裸裸的告訴你這是二分圖。明顯地求Maximum Independent Set。輕輕用簡單的二分圖匹配就搞定了。
至於難版的那個，只是沒有這般赤裸裸而已…
2009年7月16日 星期四
UVa 11504 Dominos
題目大意就是給出
塊骨牌，
個關係，每個關係以x y表示「如果骨牌x倒了，骨牌y也會倒下」。
問最少要推多少塊骨牌才會讓所有骨牌倒下。
最初蠢蠢的以為只求離散集的個數便成，結果沒留意到x y不代表y x，所以離散集會誤以為兩者關係相等，必然出錯。
細心留意，可以兩個觀察。
(1) 如果存在x使得沒有z x的話，我們必須推x。(Topological Sort即便如此)
(2) 若果有一個群組中每一塊骨牌都可以直接或間接以關係把其餘所有骨牌推下，則只需推其一塊便等於把群組中的每塊骨牌推一下，省力省時。
(2)的對群組的定義便正正是強連通塊(Strongly Connected Components)的詮釋。因為「推一塊便等於推其他塊」的想法下，我們不妨把這個塊縮成一點，並把當中骨牌成員的出入塊的邊保留。結合(1)的想法，毋需做拓撲排序，直接計算入邊為零的點(若未屬任何塊，當然它自己也可以成一塊)或塊即成。
問最少要推多少塊骨牌才會讓所有骨牌倒下。
最初蠢蠢的以為只求離散集的個數便成，結果沒留意到x y不代表y x，所以離散集會誤以為兩者關係相等，必然出錯。
細心留意，可以兩個觀察。
(1) 如果存在x使得沒有z x的話，我們必須推x。(Topological Sort即便如此)
(2) 若果有一個群組中每一塊骨牌都可以直接或間接以關係把其餘所有骨牌推下，則只需推其一塊便等於把群組中的每塊骨牌推一下，省力省時。
(2)的對群組的定義便正正是強連通塊(Strongly Connected Components)的詮釋。因為「推一塊便等於推其他塊」的想法下，我們不妨把這個塊縮成一點，並把當中骨牌成員的出入塊的邊保留。結合(1)的想法，毋需做拓撲排序，直接計算入邊為零的點(若未屬任何塊，當然它自己也可以成一塊)或塊即成。
訂閱：
文章 (Atom)
