题目大意

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

分析

  是一个最大匹配问题；

  输入时判断每一只地鼠分别可以去哪些洞，连线。

 

代码

var  a:array[1..5000,1..5000] of boolean;  v:array[1..30000] of boolean;  x,y:array[1..10000] of real;  st:array[1..30000] of longint;  i,j,k:longint;  x1,y1:real;  n,m,nm:longint;  z:longint;  v1,s:longint;function find(r:longint):boolean;var  i,j,k:longint;begin  find:=true;  for i:=1 to n do    begin      if not v[i] and a[r,i]        then          begin            k:=st[i]; st[i]:=r; v[i]:=true;            if (k=0) or find(k) then exit;            st[i]:=k;          end;    end;  find:=false;end;procedure main;var  i,j,k:longint;  z:boolean;begin  for i:=1 to n do    begin      fillchar(v,sizeof(v),0);      z:=find(i);    end;  end;begin  readln(nm);  for z:=1 to nm do    begin      fillchar(a,sizeof(a),false);      fillchar(st,sizeof(st),0);      readln(n,m,s,v1);      for i:=1 to n do        readln(x[i],y[i]);      for i:=1 to m do        begin          readln(x1,y1);          for j:=1 to n do            begin              if sqrt(sqr(x[j]-x1)+sqr(y[j]-y1))/v1<=s                then                  a[j,i]:=true            end;        end;      main;      j:=0;      for i:=1 to m do        if st[i]<>0 then j:=j+1;      writeln(n-j);    end;end.