POJ 2536 Gopher II(二分图的最大匹配)
2024-08-22 07:11:07
题目链接:http://poj.org/problem?id=2536
题意:已知有n仅仅老鼠的坐标,m个洞的坐标,老鼠的移动速度为V,S秒以后有一仅仅老鹰要吃老鼠,问有多少个老鼠被吃。
非常明晰,二分匹配,老鼠为X集合,洞为Y集合
思路:计算当前老鼠 Xi 到达洞 Yi 的时间(dis/v),假设小于S的话,则Xi与Yi联通,
被吃的老鼠数 = n - 最大匹配数
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 310;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b int n,m,s,v,ma[500][500];
bool vis[500];
int line[500];
struct node
{
double x,y;
};
node g[300],h[300]; int DFS(int u)
{
for(int v = 1;v<=m;v++)
{
if(!vis[v]&&ma[u][v])
{
vis[v]=1;
if(line[v]==-1 || DFS(line[v]))
{
line[v] = u;
return 1;
}
}
}
return 0;
}
int K_M()
{
memset(line,-1,sizeof(line));
int ans=0;
for(int i = 1;i<=n;i++)
{
init(vis);
ans += DFS(i);
}
return ans;
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&s,&v)!=EOF)
{
init(ma);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&g[i].x,&g[i].y);
}
for(int i=1;i<=m;i++)
{
scanf("%lf%lf",&h[i].x,&h[i].y);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
double dis = sqrt((h[j].x-g[i].x)*(h[j].x-g[i].x)+(h[j].y-g[i].y)*(h[j].y-g[i].y));//老鼠与洞的距离 if(dis / v <= (double)s)//老鼠到达洞的时间<S
{
ma[i][j] = 1;
}
}
}
int ans = K_M();
printf("%d\n",n - ans);
}
return 0;
}
最新文章
- MMORPG大型游戏设计与开发(服务器 游戏场景 掉落与网络连接)
- javascript各种宽高
- 通过样式class 判断多个checkbox redio 是否都选中
- I hate it
- N! HDU 1042
- MongoDB,HDFS, Spark to 电影推荐
- octopress添加回到顶部按钮
- javascript高级知识分析——函数访问
- Linux+Apache+Mysql+Php
- PHP草根论之设计模式-訪问者模式
- Ubuntu下OpenVPN客户端配置教程
- 在用jQuery时遇到的小问题
- IntelliJ IDEA配置Maven
- ubuntu16.04 backup and restore
- C#字典Dictionay多线程读是否是安全的
- Dubbo集群容错
- FireDAC 下的 Sqlite [9] - 关于排序
- Linux服务器安全之用户密钥认证登录
- WPF中使用相对资源来进行绑定,数据源是通过DataContext来指定的
- 「小程序JAVA实战」小程序头像图片上传(上)(43)
热门文章
- [Machine Learning (Andrew NG courses)]IV.Linear Regression with Multiple Variables
- 学习VC MFC开发必须了解的常用宏和指令
- C/C++ Resources
- web.xml中listener作用及使用
- 3TB硬盘的容量已经超出了传统分区标准的支持
- QT插件开发方式(没看懂)
- 使用PageHeap.EXE或GFlags.EXE检查内存越界错误
- ANDROID L——Material Design综合应用(Demo)
- thinkPHP 空模块和空操作、前置操作和后置操作 详细介绍(十四)
- CF 316C2(Tidying Up-二分图最大边权)