TOJ 2380 Gopher II 二分图最大匹配

2024-03-29 13:18

本文主要是介绍TOJ 2380 Gopher II 二分图最大匹配,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

The gopher family, having averted the canine threat, must face a new predator. 

The are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.

输入

The input contains several cases. The first line of each case contains four positive integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances are in metres; all times are in seconds; all velocities are in metres per second.

输出

Output consists of a single line for each case, giving the number of vulnerable gophers.

样例输入

2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0

20.0 20.0

样例输出

1

这道题题意比较绕...说是有n只地鼠,m个洞,老鹰的到达地面的时间s,地鼠的移动速度v,求多少只地鼠会被老鹰吃了。这个建立二分图的话,要把地鼠和洞看成两个集合。然后只有当地鼠到洞的时间少于老鹰到地面的时间才连边。

#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ma[505][505],vis[505],dx[505];
struct point  
{  double x,y;  
}G[200],H[200]; 
double dis(point p1,point p2)  
{//计算地鼠到洞的时间 return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));  
}  
int find(int i)
{for(int j=n+1;j<=n+m;j++){if(ma[i][j]&&vis[j]==0){vis[j]=1;if(dx[j]==-1||find(dx[j])){dx[j]=i;return 1;}}}return 0;
}
int main()
{int t,i,j,s,v,x,y,sum; while(scanf("%d%d%d%d",&n,&m,&s,&v)!=EOF){if(t==0)break;memset(ma,0,sizeof ma);memset(vis,0,sizeof vis);memset(dx,-1,sizeof dx);for(i=1;i<=n;i++)  scanf("%lf%lf",&G[i].x,&G[i].y);  for(i=1;i<=m;i++)scanf("%lf%lf",&H[i].x,&H[i].y);  for(i=1;i<=n;i++){  for(j=1;j<=m;j++){  double d=dis(G[i],H[j]);  if(d/v<=(double)s)//比老鹰快才安全 ma[i][n+j]=1;  }  }  sum=0;for(i=1;i<=n;i++){memset(vis,0,sizeof vis);sum+=find(i);}printf("%d\n",n-sum);}
} 

 

这篇关于TOJ 2380 Gopher II 二分图最大匹配的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858695

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta