题解 UVA10080 【Gopher II】

⚡LZSY01_XZY⚡ · 2019-07-12 09:29:28 · 题解

这题是二分图匹配中较简单的一题了。要是没有学过二分图，建议来\color{#ff0481}\small\texttt{这里}看看。

这一题，很容易想到将鼹鼠与地洞连边，建立二分图，然后计算最大匹配，答案就是鼹鼠数减去最大匹配数。至于连边的方法就是计算距离，当距离比上速度小于等于老鹰来的时间，就连边。

code:

#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN=105;
const int MAXM=100005;
int n,m,s,v,now,ans,id;

struct dot
{
    double x,y;

    double cost(struct dot tmp)
    {
        return sqrt((x-tmp.x)*(x-tmp.x)+(y-tmp.y)*(y-tmp.y));
    }
}mal[MAXN],hole[MAXN];

struct edge
{
    int v,nx;
}set[MAXM];
int head[MAXN],chk[MAXN],match[MAXN];

inline void Addedge(int u,int v)
{
    id++;set[id].v=v;set[id].nx=head[u];
    head[u]=id;
}

inline bool dfs(int u)
{
    for (int k=head[u];k>0;k=set[k].nx)
        if (chk[set[k].v]!=now)
        {
            chk[set[k].v]=now;
            if ((match[set[k].v]==-1)||dfs(match[set[k].v]))
            {
                match[set[k].v]=u;return true;
            }
        }
    return false;
}

int main()
{
    while (~scanf("%d%d%d%d",&n,&m,&s,&v))
    {
        id=0;now=0;ans=0;
        memset(chk,0,sizeof(chk));
        memset(head,-1,sizeof(head));
        memset(match,-1,sizeof(match));
        for (int i=1;i<=n;i++) scanf("%lf%lf",&mal[i].x,&mal[i].y);
        for (int i=1;i<=m;i++) scanf("%lf%lf",&hole[i].x,&hole[i].y);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                if (mal[i].cost(hole[j])/(v*1.0)<=s) Addedge(i,j);
        for (int i=1;i<=n;i++)
        {
            now++;
            if (dfs(i)) ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}