题意分析

有 $n$ 个地鼠和 $m$ 个洞，每个洞只能容纳 $1$ 只地鼠，当鹰飞来时，$n$ 个地鼠若能在 $s$ 秒内从当前位置回到洞中，就能不被鹰抓住，每只地鼠的速度为 $v$，求被抓住的地鼠个数的最小值。

解题思路

将地鼠与洞看做二分图，如果一个地鼠能在 $s$ 秒内到达洞，那么就在其之间建立一条边，根据题意，$被抓住的个数=n-最大匹配数$。

C++代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
double s,v;
vector<int>a[105];

bool vis[105];
int par[105];
struct node
{
    double x;
    double y;
};
node w[105];///老鼠位置
node h[105];///洞口位置

double dis( int i,int j )
{
    return sqrt( (w[i].x-h[j].x)*(w[i].x-h[j].x) + (w[i].y-h[j].y)*(w[i].y-h[j].y)  );
}

bool dfs(int x)
{
    int len=a[x].size();
    for(int i=0;i<len;i++)
    {
        int next=a[x][i];///可以到达的洞口
        if( !vis[next] )///本次深搜中没有被访问过
        {
            vis[next]=true;
            if( !par[next] || dfs( par[next] ) )///这个洞口没有被其他老鼠占领 或者 占领该洞口的老鼠可以找到别的洞口
            {
                par[next]=x;///next的占领者为x，用于以后的回溯
                return true;
            }
        }
    }
    return false;
}


int main()
{
    while(scanf("%d %d %lf %lf",&n,&m,&s,&v)!=EOF)
    {

        memset(par,0,sizeof(par));///清空操作
        for(int i=1;i<=n;i++)
            a[i].clear();

        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&w[i].x,&w[i].y);
        for(int i=1;i<=m;i++)
            scanf("%lf%lf",&h[i].x,&h[i].y);

        double d=s*v;///逃命距离
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {

                if( dis(i,j)<=d )///到的洞口距离 小于 逃命距离
                    a[i].push_back(j);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,false,sizeof(vis));
            if(!dfs(i)) ///没看清题意wa了好多发
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}