栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 2536 Gopher II

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 2536 Gopher II

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;const int N=1005,M=N*N;int head[N],list[M],next[M],tot;void add(int a,int b){tot++;list[tot]=b;next[tot]=head[a];head[a]=tot;}bool vis[N];int fa[N];bool dfs(int v){for(int i=head[v];i;i=next[i]){int u=list[i];if(!vis[u]){vis[u]=1;if(fa[u]==0||dfs(fa[u])){fa[u]=v;return 1;}}}return 0;}int n,m,s,v;double x[N],y[N];double d;double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int main(){while(scanf("%d%d%d%d",&n,&m,&s,&v)!=EOF){memset(head,0,sizeof head);memset(x,0,sizeof x);memset(y,0,sizeof y);memset(fa,0,sizeof fa);tot=0;d=s*v;for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for(int i=1;i<=m;i++){double a,b;scanf("%lf%lf",&a,&b);for(int j=1;j<=n;j++){if(dis(x[j],y[j],a,b)<d)add(j,n+i);}}int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);if(dfs(i))ans++;}printf("%dn",n-ans);}}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/378161.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号