vijos1212 Way Selection

vijos1212 Way Selection

​​ 他想知道怎么逃生

描述

小杉家族r个人正在一片空地上散步，突然，外星人来了…… 留给小杉家族脱逃的时间只有t秒，每个小杉都有一个跑的速度v 总共有a个传送点，小杉们必须在t秒内到达传送点才能脱逃 另外一个小杉进入一个传送点以后，该传送点就会消失 现在请你安排一种方案，使脱逃的小杉尽可能的多

格式

输入格式

每组测试数据的 第一行有三个整数r和a和t(0< a,r,t<=1000) 第二行有a对实数，第i对数表示第i个传送点的坐标，这些坐标绝对值均不超过1e6 接下来r行，每行有三个实数x,y,v，表示第i个小杉的坐标和奔跑的速度

输出格式

对每组测试数据输出一行 仅有一个整数s 表示最多有多少个小杉能成功脱逃

样例1

样例输入1

1 1 1 1 1 1 1 1 Copy 样例输出1

1 Copy 限制

每个测试点1s

提示

简单的很，别想复杂了

来源

lolanv

#include#include#define N 1100struct node{ int y,next;}data[N*N];double x1,y1,v,x[N],y[N];int a,r,t,girl[N],h[N];bool used[N];inline bool judge(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y; if (used[y]) continue;used[y]=true; if(!girl[y]||judge(girl[y])){ girl[y]=x;return true; } } return false;}int main(){ freopen("vijos1212.in","r",stdin); while (~scanf("%d%d%d",&r,&a,&t)){ memset(h,0,sizeof(h));int num=0;memset(girl,0,sizeof(girl)); for (int i=1;i<=a;++i)scanf("%lf%lf",&x[i],&y[i]); for (int i=1;i<=r;++i){ scanf("%lf%lf%lf",&x1,&y1,&v); for (int j=1;j<=a;++j){ if ((x1-x[j])*(x1-x[j])+(y1-y[j])*(y1-y[j])<=v*t*v*t){ data[++num].y=j;data[num].next=h[i];h[i]=num; } } }int cnt=0; for (int i=1;i<=r;++i){ memset(used,0,sizeof(used)); if(judge(i)) cnt++; } printf("%d\n",cnt); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。