题目
Description
1000MS/65536K
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.
Input
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
Output consists of a single line for each case, giving the number of vulnerable gophers.
Simple input
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0
Simple output
1
题目分析
这道题比较简单，花了接近9分钟才做出来体现了我能力的不足。题目的意思是给你n个鼹鼠和m个洞并且给你鼹鼠和洞的坐标以及鼹鼠的速度和它们可以利用的时间，求鼹鼠与洞的最大匹配数。求出（每只）妹纸鼹鼠与洞的距离并且求出它们是否能在规定的时间里抵达，能则建立连线，不能就呵呵。最后裸一个匈牙利就过了。我是不是很帅！
AC代码
8620K/188MS1
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define N 1005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int useif[N]; //记录y中节点是否使用 0表示没有访问过，1为访问过
int link[N]; //记录当前与y节点相连的x的节点
int mat[N][N]; //记录连接x和y的边，如果i和j之间有边则为1，否则为0
int gn,gm; //二分图中x和y中点的数目
//char mapp[N][N];
int mat1[N][N];
double x[1050],y[1050];
struct nod
{
double a,b,c;
};
nod f[1050];
int can(int t)
{
int i;
for(i=1;i<=gm;i++)
{
if(useif[i]==0 && mat[t][i])
{
useif[i]=1;
if(link[i]==-1 || can(link[i]))
{
link[i]=t;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int i,num;
num=0;
memset(link,0xff,sizeof(link));
for(i=1;i<=gn;i++)
{
memset(useif,0,sizeof(useif));
if(can(i))
num++;
}
return num;
}
void init()
{
memset(useif,0,sizeof(useif));
memset(link,0,sizeof(link));
memset(mat,0,sizeof(mat));
//memset(mapp,0,sizeof(mapp));
memset(mat1,0,sizeof(mat1));
}
int main()
{
int m,n,s,v;
while(scanf("%d%d%d%d",&n,&m,&s,&v)!=EOF)
{
init();
for(int i=1;i<=m;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&f[i].a,&f[i].b);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i].c=sqrt((f[i].a-x[j])*(f[i].a-x[j])+(f[i].b-y[j])*(f[i].b-y[j]));
double t=double(f[i].c/v);
if(t<=s)
mat[i][j]=1;
else mat[i][j]=0;
}
}
gn=m;
gm=n;
int ans=MaxMatch();
printf("%d\n",n-ans);
}
}