網頁

2014年5月8日 星期四

UVa 10080 Gopher II

題意:
    有N個地鼠和M個地鼠洞,每個點都有座標(x,y),因此每隻地鼠和每個地鼠洞之間有不同的距離,每隻地鼠的移動速度都是v,現在有老鷹會在s秒後抓沒有跑進洞的地鼠,一個地鼠洞只能藏一隻地鼠,求沒有躲到洞裡被老鷹抓走的地鼠的最少數量為?

想法:
    地鼠在左邊,地鼠洞在右邊,把每隻地鼠與能在時間內跑到的地鼠洞都建一條邊,然後做最大匹配,答案就是(地鼠數量-最大匹配數)。