php做网站 价格/最有效的app推广方式有哪些

地鼠的困境

Time Limit:1000MS Memory Limit:65536K

Description

地鼠家族面临着一个新的威胁——猎食者。
　　地鼠家族一共有N个地鼠和M个鼠洞，每个都位于不同的(x, y)坐标中。假如有地鼠在发觉危险以后s秒内都没有回到鼠洞里的话，就可能成为老鹰的食物。当然了，一个鼠洞只能拯救一只地鼠的命运，所有地鼠都以相等的速度v移动。地鼠家族需要设计一种策略，使得老鹰来时，易受攻击的地鼠数量最少。

Input

本题有多组数据。第1行为测试数据组数T(T<=50)。
对于每组数据，第一行4个整数n, m, s和v(n, m <= 100)。以后n行为地鼠的坐标，以后m行为鼠洞的坐标。距离的单位是m，时间的单位是s，速度的单位是m/s。

Output

对于每组数据输出一行，为易受攻击的地鼠的数量。

Sample Input

1
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Sample Output

1

分析：

其实这道题就是二分图最大匹配的模板题 只不过最后要$n-ans$ 因为匹配上的是要被抓的
求的是能获救的 还有 这个数据给的很🐶 实际$ta$要输入多组数据 输出还要换行

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
using namespace std;
int n,m,s,T,v,tot,head[105],link[105],cover[105];
double x[105],y[105];
struct node{int to,next;}a[205];  //邻接表
void add(int x,int y){a[++tot]=(node){y,head[x]};head[x]=tot;}
int find(int x)  //最大匹配模板
{for(int i=head[x];i;i=a[i].next){int qwq=a[i].to;if(!cover[qwq]){cover[qwq]=1;int qaq=link[qwq];link[qwq]=x;if(!qaq||find(qaq)) return true;link[qwq]=qaq; }} return false;
} 
int main(){scanf("%d",&T);while(T--){scanf("%d%d%d%d",&n,&m,&s,&v);for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for(int i=1;i<=m;i++){double xx,yy;scanf("%lf%lf",&xx,&yy);for(int j=1;j<=n;j++){double dis=sqrt((xx-x[j])*(xx-x[j])+(yy-y[j])*(yy-y[j]));  //求距离if(s*v>=dis)add(j,i);} }int ans=0;for(int i=1;i<=n;i++){memset(cover,0,sizeof(cover));if(find(i)) ans++;}printf("%d\n",n-ans);tot=0;memset(head,0,sizeof(head));  //做一次清空一次memset(link,0,sizeof(link));}return 0;
}