<span>UPCOJ2985 Gopher（二分匹配）</span>
这道题是我们弱校大一校赛的防AK题。。。
当时不到1个半小时做完其他题就一直在看他
然而当时并没有学二分匹配
然后就各种结构体sort。。。
整了3个多小时还是败了
于是学习了一下，这就很简单了
题意就是给你n个老鼠m个洞，并给你坐标和老鼠的速度和最晚时间
通过这些距离算出每个老鼠对于每个洞能否在规定时间内进去。。
然后就。。。好了
/* *********************************************** Author :devil Created Time :2016/4/8 23:53:26 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; double x1[110],x2[110],yy[110],y2[110]; bool vis[110]; int n,m,s,v,linker[110]; vector<int>eg[110]; int dfs(int u) { for(int i=0;i<eg[u].size();i++) { int to=eg[u][i]; if(!vis[to]) { vis[to]=1; if(linker[to]==-1||dfs(linker[to])) { linker[to]=u; return 1; } } } return 0; } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d%d%d%d",&n,&m,&s,&v)) { for(int i=0; i<n; i++) eg[i].clear(); memset(linker,-1,sizeof(linker)); for(int i=0; i<n; i++) scanf("%lf%lf",&x1[i],&yy[i]); for(int i=0; i<m; i++) scanf("%lf%lf",&x2[i],&y2[i]); v=v*s*v*s; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { double p=(x1[i]-x2[j])*(x1[i]-x2[j])+(yy[i]-y2[j])*(yy[i]-y2[j]); if(p<=v) eg[i].push_back(j); } } int ans=0; for(int i=0; i<n; i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d\n",n-ans); } return 0; }
Momenta公司福利 295人发布
投递蚂蚁集团等公司10个岗位 >