题目描述

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

思路

将每一个地鼠和可以到达的动连边，然后跑最大匹配就可以了

#include <stdio.h>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
#define maxn 101
#define fill(x, y) memset(x, y, sizeof(x))
int n, m, s, v;
double sqr(double a){return a * a;}
int link[maxn];
struct arr
{
    double x, y;
}a[maxn];
arr b[maxn];
bool map[maxn][maxn], fl[maxn];
int find(int x)
{
    for (int i = 1; i <= n; i++)
        if (map[x][i] && ! fl[i])
        {
            int q = link[i]; link[i] = x; fl[i] = 1;
            if (q == 0 || find(q)) return true;
            link[i] = q;
        } 
    return false;
}
int tot()
{
    int ans = 0;
    fill(link, 0);
    for (int i = 1; i <= n; i++)
    {
        fill(fl, false);
        if (find(i)) ans++;
    }
    return ans;
}
int main()
{
    int o;
    scanf("%d", &o);
    for (int k = 1; k <= o; k++)
    {
        fill(map, 0);
        scanf("%d%d%d%d", &n, &m, &s, &v);
        for (int i = 1; i <= n; i++)
            scanf("%lf%lf", &a[i].x, &a[i].y);
        for (int i = 1; i <= m; i++)
            scanf("%lf%lf", &b[i].x, &b[i].y);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (sqrt(sqr(a[i].x - b[j].x) + sqr(a[i].y - b[j].y)) <= s * v)
                    map[i][j] = 1;
        printf("%d\n", n - tot());
    }
}