題目：http://poj.org/problem?id=3020
最大40*10的棋盤上有一些「*」或是「o」
想用2*1的骨牌蓋住所有的*、求最少要幾張骨牌(可以重疊)
程式碼：http://codepad.org/Rswm24wE
原來！原來我不會寫最大二分匹配…
(卡了N久的一題)
首先把每個*想成一個個節點、*之間相鄰就是有邊相連
這時候發現，放骨牌就等同於是「選邊」
想要選最少的邊讓全部的點都蓋到，這就是充滿愉悅智慧的「最小邊覆蓋」問題
於是總點數-最大二分匹配數即答案
結論就是
我要去打Blaze rod來玩藥水了，大家88
沒有留言:
張貼留言