(ssl1333)地鼠的困境

本文主要是介绍(ssl1333)地鼠的困境，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

地鼠的困境

Description

　　地鼠家族面临着一个新的威胁——猎食者。
　　地鼠家族一共有N个地鼠和M个鼠洞，每个都位于不同的(x, y)坐标中。假如有地鼠在发觉危险以后s秒内都没有回到鼠洞里的话，就可能成为老鹰的食物。当然了，一个鼠洞只能拯救一只地鼠的命运，所有地鼠都以相等的速度v移动。地鼠家族需要设计一种策略，使得老鹰来时，易受攻击的地鼠数量最少。

Input

本题有多组数据。第1行为测试数据组数T(T<=50)。
对于每组数据，第一行4个整数n, m, s和v(n, m <= 100)。以后n行为地鼠的坐标，以后m行为鼠洞的坐标。距离的单位是m，时间的单位是s，速度的单位是m/s。

Output

对于每组数据输出一行，为易受攻击的地鼠的数量。

Sample Input

1
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Sample Output

1

Source

elba

   题解：本题依旧是最大匹配~（详见：这里）
      本题要找最少被攻击的地鼠，故要匹配出最大安全地鼠的匹配。
      至于一开始怎么判断i地鼠可不可以进j地洞，可以路程除速度，看可否在规定时间内逃进地洞，路程便需要勾股定理求出(两点之间，直线最短)
      最后求出最大匹配数，输出即可╰(· ▽ ·)╯

vara:array[1..100,1..100]of boolean;c:array[1..100]of boolean;l:array[1..100,1..2]of real;link:array[1..100]of longint;t,n,m,s,v,i,j,k,ans:longint;x,y,z:real;
function try(i:longint):boolean;//匈牙利算法
varj,t:longint;
begintry:=true;for j:=1 to n doif (a[i,j]) and not(c[j]) thenbegint:=link[j]; link[j]:=i; c[j]:=true;if (t=0) or try(t) then exit;link[j]:=t;end;try:=false;
end;
beginread(t);for k:=1 to t dobeginread(n,m,s,v);for i:=1 to n do read(l[i,1],l[i,2]);for i:=1 to m dobeginread(x,y);for j:=1 to n dobeginz:=sqrt(sqr(x-l[j,1])+sqr(y-l[j,2]));//勾股定理if z/v<=s then a[i,j]:=trueelse a[i,j]:=false;end;end;fillchar(link,sizeof(link),0);for i:=1 to n dobeginfillchar(c,sizeof(c),0);try(i);end;ans:=0;for i:=1 to n doif link[i]=0 then inc(ans);writeln(ans);end;
end.

这篇关于(ssl1333)地鼠的困境的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---