題目網址: http://goo.gl/5Xdcr7
題 意: 有 n 隻地鼠， m 個地洞，告訴你地鼠、地洞的座標，還有地鼠的速度 v，此時天上有隻老鷹，當老鷹飛下來時，地鼠若無法在 s 時間內跑近地洞，就會被老鷹吃掉，且一個地洞只能容納一隻地鼠，問最後能有幾隻地鼠會被攻擊。
解法: 分成地鼠與地洞兩個集合，地鼠要配地洞，很明顯就是二分匹配(bipartite matching)唷，只要符合地鼠到地洞的距離小於等於 s * v，就把該地鼠與該地洞建邊，接著用 bipartite matching 演算法就可解。
TAG: Bipartite Matching
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽