<题目链接>
题目大意：
有m个宾客，n把雨伞，预计时间t后将会下大雨，告诉你每个宾客的位置和速度，每把雨伞的位置，问你最多几个宾客能够拿到伞。
解题分析：
本题就是要我们求人与伞之间的最大匹配，但是数据量较大，匈牙利算法复杂度为$O(n \times m)$，会超时，所以这里用的是复杂度为$O(\sqrt{n} \times m)$的HK算法。
当然，本题也可以用Dinic最大流来求解最大匹配，并且这种方法求得到最大匹配的时间复杂度也为$O(sqrt(n)*m)$
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int M = +;
struct point{
double x,y,s;
}a[M],b[M];
bool map[M][M];
bool vis[M];
int dx[M],dy[M];/*dx[i]表示左集合i顶点的距离编号，dy[i]表示右集合i顶点的距离编号,还有就是这里就是bfs找增广路用的数组 对于u-->v可达就有dy[v] = dx[u] + 1 */
int cx[M],cy[M];
int dis;
int n,T,m;
bool searchpath()
{
queue<int>q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<=n;i++)
{
//cx[i]表示左集合i顶点所匹配的右集合的顶点序号
if(cx[i]==-)
{
//将未遍历的节点 入队 并初始化次节点距离为0
q.push(i);
dx[i]=;
}
}
//广度搜索增广路径
while(!q.empty())
{
int u=q.front();
q.pop();
if(dx[u]>dis) break;
//取右侧节点，所以用m。
for(int v=;v<=m;v++)
{
//右侧节点的增广路径的距离
if(map[u][v]&&dy[v]==-)
{
dy[v]=dx[u]+;//v对应的距离 为u对应距离加1
if(cy[v]==-) dis=dy[v];
else
{
dx[cy[v]]=dy[v]+;
q.push(cy[v]);
}
}
}
}
return dis!=INF;
}
//寻找路径 深度搜索
int dfs(int u)
{
for(int v=;v<=m;v++)
{
//如果该点没有被遍历过 并且距离为上一节点+1
if(map[u][v]&&!vis[v]&&dy[v]==dx[u]+)
{
//对该点染色，即是进行标记
vis[v]=true;
if(cy[v]!=-&&dy[v]==dis)
continue;
if(cy[v]==-||dfs(cy[v]))
{
cx[u]=v;
cy[v]=u;
return ;
}
}
}
return ;
}
//得到最大匹配的数目
int MaxMatch()
{
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
int res=;
while(searchpath())
{
memset(vis,false,sizeof(vis));
for(int i=;i<=n;i++)
{
if(cx[i]==-)
res+=dfs(i);
}
}
return res;
}
int main()
{
int t,k=;
scanf("%d",&t);
while(t--)
{
memset(map,false,sizeof(map));
scanf("%d",&T);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].s);
scanf("%d",&m);
for(int i=;i<=m;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(a[i].s*T>=sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y)))
map[i][j]=true;
}
int ans=MaxMatch();
printf("Scenario #%d:\n%d\n\n",k++,ans);
}
}
HK