POJ2536 Gopher II

二分图的最大匹配

地鼠内部和地鼠洞内部都是没有边相连的，那么就可以看成一个二分图。地鼠如果可以跑到那个地鼠洞，就连一条边，然后跑二分图的最大匹配，最后地鼠的数量减去最大匹配数就是答案。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN=;

int nx,ny;

int g[MAXN][MAXN];

int cx[MAXN],cy[MAXN];

int mk[MAXN];

int n;

double s,v;

double H=1e-;

struct P

{

    double x,y;

} M[MAXN],D[MAXN];

int path(int u)

{

    for(int v=; v<ny; v++)

    {

        if(g[u][v]&&!mk[v])

        {

            mk[v]=;

            if(cy[v]==-||path(cy[v]))

            {

                cx[u]=v;

                cy[v]=u;

                return ;

            }

        }

    }

    return ;

}

int MaxMatch()

{

    int res=;

    memset(cx,-,sizeof(cx));

    memset(cy,-,sizeof(cy));

    for(int i=; i<nx; i++)

    {

        if(cx[i]==-)

        {

            memset(mk,,sizeof(mk));

            res=res+path(i);

        }

    }

    return res;

}

bool ok(const P&a,const P&b)

{

    if(s*v-sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))>=H)

        return ;

    return ;

}

int main()

{

    int i,j;

    while(~scanf("%d%d%lf%lf",&nx,&ny,&s,&v))

    {

        memset(g,,sizeof(g));

        for(i=; i<nx; i++)

            scanf("%lf%lf",&M[i].x,&M[i].y);

        for(i=; i<ny; i++)

            scanf("%lf%lf",&D[i].x,&D[i].y);

        for(i=; i<nx; i++)

            for(j=; j<ny; j++)

                if(ok(M[i],D[j]))

                    g[i][j]=;

        printf("%d\n",nx-MaxMatch());

    }

    return ;

}