Vijos-P1212Way 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
1
限制
每个测试点1s
第一次做这种需要自己建图的最大匹配（虽然不是很难），但也算进步了。。。
可惜的是我居然交了几次！可怜的double啊。。。。还有一次居然把 i 和 j 打错了
测评情况（Vijos）
C++ AC Code
/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<cmath>
#include<cstring>
#define sqr(_) ((_)*(_))
const int N=1000+10;
int r,a,t;
struct node{double x,y,v;}send[N],p[N];
int g[N][N],hash[N];
int pre[N];
void read()
{
scanf("%d%d%d",&r,&a,&t);
for(int i=1;i<=a;i++) scanf("%lf%lf",&send[i].x,&send[i].y);
for(int i=1;i<=r;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].v);
}
inline double dis(double x,double y,double a,double b)
{
return sqrt(sqr(x-a)+sqr(y-b));
}
void build_map()
{
for(int i=1;i<=r;i++)
for(int j=1;j<=a;j++)
{
double s=dis(p[i].x,p[i].y,send[j].x,send[j].y);
double time=s/p[i].v;
if(time>t) continue;
g[i][j]=1;
}
}
int search(int x)
{
for(int i=1;i<=a;i++)
if(g[x][i]&&!hash[i])
{
hash[i]=1;
if(pre[i]==-1||search(pre[i]))
{
pre[i]=x;
return 1;
}
}
return 0;
}
void work()
{
build_map();
int res=0;
memset(pre,-1,sizeof(pre));
for(int i=1;i<=r;i++)
{
memset(hash,0,sizeof(hash));
if(search(i)) res++;
}
printf("%d\n",res);
}
int main()
{
freopen("p1212.in","r",stdin);
freopen("p1212.out","w",stdout);
read();
work();
return 0;
}