当前位置: 代码迷 >> 综合 >> 地鼠的困境 ssl1333(不一定对)
  详细解决方案

地鼠的困境 ssl1333(不一定对)

热度:47   发布时间:2023-10-09 12:54:05.0

题目大意

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

题解
把每一只老鼠和可以去的洞连线,最大匹配。

function find(p:longint):longint;

var

  t,q:longint;

begin

  find:=true;

  t:=ls[p];

  while t>0 do

    with g[t] do

      begin

        if v[y]=0 then

          begin

            v[y]:=1;

            q:=link[y];

            link[y]:=p;

            if (q=0) or find(q) then exit;

            link[y]:=q;

          end;

        t:=next;

     end;

  find:=false;

end;

procedure match;

var

  i,ans:longint;

begin

 fillchar(link,sizeof(link),0);

 for i:=1 to n do

   begin

     fillchar(v,sizeof(v),0);

     if find(i)then ans:=ans+1;

   end;

 writeln(ans);

end;