我要评论
这道题其实也差不多是一个模板题
注意有多组数据即可。
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int T,n,m,v,s,tot,ans,link[1010],vis[1010],ls[1010];
double dzx[1010],dzy[1010],sdx,sdy;
struct node
{
int y,next;
}map[1000010];
void add(int x,int y)
{
map[++tot].y=y;
map[tot].next=ls[x];
ls[x]=tot;
}
int dfs(int x)
{
for(int i=ls[x]; i; i=map[i].next)
{
int y=map[i].y;
if(!vis[y])
{
vis[y]=1;
int fa=link[y];
link[y]=x;
if(fa==0||dfs(fa))
return 1;
link[y]=fa;
}
}
return 0;
}
int main()
{
cin>>T;
while(T--)
{
scanf("%d%d%d%d",&n,&m,&s,&v);
for(int i=1; i<=n; i++)
scanf("%lf%lf",&dzx[i],&dzy[i]);
for(int i=1; i<=m; i++)
{
scanf("%lf%lf",&sdx,&sdy);
for(int j=1; j<=n; j++)
{
double dis=sqrt((sdx-dzx[j])*(sdx-dzx[j])+(sdy-dzy[j])*(sdy-dzy[j]));
if(dis<=s*1.0*v*1.0) //能到达才建边
add(j,i);
}
}
for(int i=1; i<=n; i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
cout<<n-ans<<endl; //受到攻击的，不是不受到攻击的
memset(link,0,sizeof(link)); //数组，变量清零
memset(ls,0,sizeof(ls));
tot=0,ans=0;
}
return 0;
}
本文地址：https://blog.csdn.net/Jackma_mayichao/article/details/108163395
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论