二分图的最大匹配

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

#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 ;
}
05-12 05:50