<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;
}

 

全部评论

相关推荐

程序员猪皮:看不到八股什么意思
点赞 评论 收藏
分享
11-01 08:48
门头沟学院 C++
伤心的候选人在吵架:佬你不要的,能不能拿户口本证明过户给我。。球球了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-27 10:48
点赞 评论 收藏
分享
评论
点赞
收藏
分享
正在热议
# 25届秋招总结 #
443173次浏览 4517人参与
# 春招别灰心,我们一人来一句鼓励 #
42122次浏览 537人参与
# 阿里云管培生offer #
120397次浏览 2220人参与
# 地方国企笔面经互助 #
7973次浏览 18人参与
# 同bg的你秋招战况如何? #
77083次浏览 569人参与
# 实习必须要去大厂吗? #
55804次浏览 961人参与
# 北方华创开奖 #
107467次浏览 600人参与
# 虾皮求职进展汇总 #
116163次浏览 886人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
11668次浏览 289人参与
# 实习,投递多份简历没人回复怎么办 #
2454912次浏览 34860人参与
# 提前批简历挂麻了怎么办 #
149924次浏览 1978人参与
# 在找工作求抱抱 #
906075次浏览 9421人参与
# 如果公司给你放一天假,你会怎么度过? #
4762次浏览 55人参与
# 你投递的公司有几家约面了? #
33209次浏览 188人参与
# 投递实习岗位前的准备 #
1196021次浏览 18550人参与
# 机械人春招想让哪家公司来捞你? #
157643次浏览 2267人参与
# 双非本科求职如何逆袭 #
662359次浏览 7397人参与
# 发工资后,你做的第一件事是什么 #
12798次浏览 62人参与
# 工作中,努力重要还是选择重要? #
35896次浏览 384人参与
# 简历中的项目经历要怎么写? #
86935次浏览 1516人参与
# 参加完秋招的机械人,还参加春招吗? #
20148次浏览 240人参与
# 我的上岸简历长这样 #
452049次浏览 8089人参与
牛客网
牛客企业服务