Vijos1212 Way Selection [2017年6月计划二分图03]

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

样例输出1

限制

每个测试点1s

提示

简单的很，别想复杂了

来源

lolanv

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <cmath>
 7 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();if(c == '-')x = -x;}
 8 const int MAXN = 1000 + 10;
 9 
10 int g[MAXN][MAXN],by[MAXN],lk[MAXN];
11 int r,a,t,ans;
12 double x[MAXN],y[MAXN],v[MAXN],xx[MAXN],yy[MAXN]; 
13 
14 int find(int v)
15 {
16     for(int i = 1;i <= a;i ++)
17     {
18         if(!by[i] && g[v][i])
19         {
20             by[i] = 1;
21             if((!lk[i]) || find(lk[i]))
22             {
23                 lk[i] = v;
24                 return 1;
25             }
26         }
27     }
28     return 0;
29 }
30 
31 int main()
32 {
33     read(r);read(a);read(t);
34     for(int i = 1;i <= a;i ++)
35         scanf("%lf %lf", &x[i], &y[i]);
36     for(int i = 1;i <= r;i ++)
37         scanf("%lf %lf %lf", &xx[i], &yy[i], &v[i]); 
38     for(int i = 1;i <= a;i ++)
39     {
40         for(int j = 1;j <= r;j ++)
41         {
42             g[j][i] = (sqrt((x[i] - xx[j]) * (x[i] - xx[j]) + (y[i] - yy[j]) * (y[i] - yy[j])) <= v[j] * t);
43         }
44     }
45     for(int i = 1;i <= r;i ++)
46     {
47         memset(by, 0, sizeof(by));
48         if(find(i))ans ++;
49     }
50     printf("%d", ans);
51     return 0;
52 }

View Code

Vijos1212 Way Selection [2017年6月计划 二分图03]