首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
uva10080专题
UVA10080 Gopher II
题意:有n只地鼠(gopher)和m个地洞,现在遇到危险,地鼠要在s秒内钻进地洞里,地鼠的速度是v,但是每个地洞只能容纳1只地鼠。给定每只地鼠和每个地洞的位置,和s,v,求将会有危险的地鼠的个数。 分析:将地鼠看成一个点,所有地鼠看成一个集合X,将地洞看成一个点,所有地洞看成另一个集合Y,如果地鼠能跑到地洞就连一条线,变成二部图,题意就变成了求二部图最大匹配问题了,套用匈牙利算法。 代码:
阅读更多...