SSL 1333 地鼠的困境#匈牙利算法#

本文主要是介绍SSL 1333 地鼠的困境#匈牙利算法#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求最少有多少只老鼠被老鹰抓。

---

分析

使用匈牙利算法，求出最大匹配，用n减去它就是答案。

---

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#define fill(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{int x,y,next;}e[10001];
double f(double k){return k*k;} 
int n,m,s,v,ans,t,c,ls[101],link[101]; 
bool cover[101]; double x1[101],y2[101];
void add(int x,int y){e[++c].x=x; e[c].y=y; e[c].next=ls[e[c].x]; ls[e[c].x]=c;}
bool find(int x){int t=ls[x];while (t){if (!cover[e[t].y]){cover[e[t].y]=1;int q=link[e[t].y];link[e[t].y]=x;if (!q||find(q)) return 1;//找增广路link[e[t].y]=q;}t=e[t].next;}return 0;
}
int main(){scanf("%d",&t);while (t--){fill(ls,0); ans=c=0; fill(link,0);scanf("%d%d%d%d",&n,&m,&s,&v);for (int i=1;i<=n;i++) scanf("%lf%lf",&x1[i],&y2[i]);for (int i=1;i<=m;i++){double o,p;scanf("%lf%lf",&o,&p);for (int j=1;j<=n;j++)if (sqrt(f(x1[j]-o)+f(y2[j]-p))<=s*v) add(j,i);}for (int i=1;i<=n;i++) ans+=(!find(i)),fill(cover,0);printf("%d\n",ans);}return 0;
}

这篇关于SSL 1333 地鼠的困境#匈牙利算法#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---