老鼠能逃到一个洞，则将他们连边，求二分图最大匹配
不写图论好长时间，对匈牙利都有些不敏感了……
#include <iostream> #include <cmath> using namespace std; struct gtype { int y,next; }g[10010]; int first[210],link[210]; bool used[210]; struct po { double x,y; }a[110],b[110]; int tot,n,m,s,v,ans; double dis(po a, po b) { return pow((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y),0.5); } void add(int x, int y) { tot++; g[tot].y=y; g[tot].next=first[x]; first[x]=tot; } bool find(int s) { int temp=first[s]; while (temp!=-1) { if (!used[g[temp].y]) { used[g[temp].y]=true; if ((link[g[temp].y]==0)||(find(link[g[temp].y]))) { link[g[temp].y]=s; return true; } } temp=g[temp].next; } return false; } int main() { int i,j; while (cin >> n >> m >> s >> v) { for (i=1;i<=n;i++) cin >> a[i].x >> a[i].y; for (i=1;i<=m;i++) cin >> b[i].x >> b[i].y; tot=0; memset(g,0,sizeof(g)); memset(first,-1,sizeof(first)); for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (v*s>=dis(a[i],b[j])) add(i,n+j); n=n+m; memset(link,0,sizeof(link)); for (i=1;i<=n;i++) { memset(used,false,sizeof(used)); find(i); } ans=n-m; for (i=1;i<=n;i++) if (link[i]!=0) ans--; cout << ans << endl; } system("pause"); return 0; }
