题目链接

题意:有n个客人,m把雨伞,在t秒之后将会下雨,给出每个客人的坐标和每秒行走的距离,以及雨伞的位置,问t秒后最多有几个客人可以拿到雨伞?

就是求最大匹配的

 Hopcroft-Karp复杂度O(sqrt(n)*m),相比匈牙利算法优化在于,Hopcroft-Karp算法每次可以扩展多条不相交增广路径。

所以只能用Hopcroft-Karp而且好像只能用邻接表来表示;

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define N 3010
#define INF 0xfffffff int vis[N], usedx[N], usedy[N], n, m;
int dx[N], dy[N], cnt, depth, head[N];
///BFS分层时,dx[] dy[]记录点所在的层,-1表示不在分层
struct node
{
int x, y, v;
} a[N], b[N];
struct Edge
{
int v, next;
}e[N*N];///用邻接表
void Add(int u, int v)
{
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt++;
} bool Find(int u)
{
for(int i=head[u]; i!=-; i=e[i].next)
{
int v = e[i].v;
if(!vis[v] && dx[u] == dy[v]-)
{
vis[v] = ;
if(!usedy[v] || Find(usedy[v]))
{
usedy[v] = u;
usedx[u] = v;
return true;
}
}
}
return false;
}
bool bfs()
{
queue<int> Q;
depth = INF;
memset(dx, -, sizeof(dx));
memset(dy, -, sizeof(dy));
for(int i=; i<=n; i++)
{
if(!usedx[i])
{
dx[i] = ;
Q.push(i);
}
}
while(!Q.empty())
{
int u = Q.front(); Q.pop();
if(depth < dx[u])
break;
for(int j=head[u]; j!=-; j=e[j].next)
{
int v = e[j].v;
if(dy[v] == -)
{
dy[v] = dx[u] + ;
if(!usedy[v])
depth = dy[v];
else
{
dx[ usedy[v] ] = dy[v] + ;
Q.push( usedy[v] );
}
}
}
}
if(depth == INF)
return false;
return true;
}
int main()
{
int T, t, x, y, t0=;
scanf("%d", &T);
while(T--)
{
cnt = ;
memset(head, -, sizeof(head));
scanf("%d%d", &t, &n);
for(int i=; i<=n; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].v);
}
scanf("%d", &m);
for(int i=; i<=m; i++)
{
scanf("%d%d", &x, &y);
for(int j=; j<=n; j++)
{
int d = (a[j].x-x)*(a[j].x-x)+(a[j].y-y)*(a[j].y-y);
if(d <= a[j].v*t*a[j].v*t)
Add(j, i);
}
}
int ans = ;
memset(usedx, , sizeof(usedx));
memset(usedy, , sizeof(usedy));
while( bfs() )
{
memset(vis, , sizeof(vis));
for(int i=; i<=n; i++)
{
if(!usedx[i] && Find(i))
ans++;
}
}
printf("Scenario #%d:\n%d\n\n", t0++, ans);
}
return ;
}

最新文章

  1. 【requireJS源码学习01】了解整个requireJS的结构
  2. UI入门指引
  3. URL(待整合到HTTP书中哦)
  4. JS之iframe中的窗口
  5. 多个电脑共用一个ssh
  6. iOS 手动打造JSON Model转换库
  7. 配置自己风格的Clang-Format-Xcode
  8. HDU 4336 Card Collector(动态规划-概率DP)
  9. 整体认识flume:Flume介绍、分布式安装、常见问题及解决方案
  10. VS快速注释
  11. Redmine入门-安装
  12. OpenBUGS抽样数据基本操作
  13. WINDOWS SERVER 2016 IE使用FLASH PLAYER的方法
  14. C语言向上、向下取整
  15. Robot Framework - 一些练习
  16. php获取URL扩展名
  17. 整合shiro出现【Correct the classpath of your application so that it contains a single, compatible version of org.quartz.Scheduler】
  18. 分享一个Godaddy的优惠码,可以优惠35%——2013-11-23
  19. Keepalived介绍以及在Linux系统下的安装与配置
  20. 百度编辑器插入视频、iframe 失败

热门文章

  1. 在PADS中,大面积覆铜有3个重要概念
  2. 【Java集合的详细研究7】Set和List 的关系与区别
  3. spark 安装配置
  4. Davlik虚拟机
  5. HttpClient传递Cookie
  6. 第二章 入门(MyBatis)
  7. 对ChemDraw Prime 16.0你了解多少
  8. ubuntu wine-qq安装
  9. Java集合----概述、Collection接口、Iterator接口
  10. Emulator Error: Could not load OpenGLES emulation library: Could not load DLL!