当前位置：网站首页>vijos1212 Way Selection

vijos1212 Way Selection

2022-08-08 14:03:00 【51CTO】

http://www.elijahqi.win/archives/1071

背景

小杉家族遭遇了前所未有的大危机
他想知道怎么逃生

描述

小杉家族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<cstdio>
       
#include<cstring>
       
#define N 1100
       
struct 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;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5555444

当前位置：网站首页>vijos1212 Way Selection

vijos1212 Way Selection

边栏推荐

猜你喜欢

随机推荐