SSL 1333 地鼠的困境#匈牙利算法# 二分图匹配

题目 【SSL 1333 地鼠的困境#匈牙利算法#】求最少有多少只老鼠被老鹰抓。
分析使用匈牙利算法，求出最大匹配，用n减去它就是答案。
代码

#include #include #include #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 地鼠的困境#匈牙利算法#

推荐阅读

000723股票行情 000723新浪财经

草莓有什么特点

半夜不能入睡

什么是日晒斑，日晒斑是怎么形成的？

厍做姓怎么读厍作为姓氏怎么念

农村房屋无证被拆怎么办农村无证房产怎么确权

2018.5.15|2018.5.15 星期二晴广州

股票600731的走势股票600731多少钱

redis多大key算大key redis的key可以多大

ShuangzhaoDB如何在金融交易系统中控制风险

火车票受让人是什么意思

超轻粘土制作小猪佩奇

刘海屏|中置圆孔还是“药丸”？iPhone 14 Pro又曝新渲染图

林俊杰曹操歌词含义林俊杰曹操歌词

法律规定怎么解除买房合同？，怎样解除购房合同

绘本讲师训练营【43期】16/21实践原创2《跑跑镇》

c语言程序设计爱心代码，求教大神这个C程序爱心代码

生化危机6 简单介绍它的由来

为什么贷款要银行流水

这三种钱，越花越有!