题目链接：
题目描述：
有n个客人，m把雨伞，在t秒之后将会下雨，给出每个客人的坐标和每秒行走的距离，以及雨伞的位置，问t秒后最多有几个客人可以拿到雨伞?
解题思路：
数据范围太大，匈牙利算法O(n*m)果断华丽丽的TLE，请教了一下度娘，发现还有一种神算法—— Hopcroft-Karp，然后就get√新技能，一路小跑过了，有一点不明白的是hdu上竟然有人0ms过，这又是什么神姿势(吓哭！！！！！)，额.........,扯远了。
Hopcroft-Karp复杂度O(sqrt(n)*m)，相比匈牙利算法优化在于，Hopcroft-Karp算法每次可以扩展多条不相交增广路径。
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f;
struct node
{
int to, next;
} edge[maxn*maxn+];
struct point
{
double x, y, num;
};
point p_gue[maxn+], p_umb[maxn+];
int head[maxn+], vis[maxn+], n, m, tot, dis;
int cx[maxn+], cy[maxn+], dx[maxn+], dy[maxn+]; void Add (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot ++;
} bool bfs ()
{//寻找多条无公共点的最短增广路
queue <int> Q;
dis = INF;
memset (dx, -, sizeof(dx));
//左边顶点i所在层编号
memset (dy, -, sizeof(dy));
//右边顶点i所在层编号
for (int i=; i<=n; i++)
if (cx[i] == -)
{
Q.push(i);
dx[i] = ;
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
if (dx[u] > dis)
break;
for (int i=head[u]; i!=-; i=edge[i].next)
{
int v = edge[i].to;
if (dy[v] == -)
{
dy[v] = dx[u] + ;
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 i=head[u]; i!=-; i=edge[i].next)
{
int v = edge[i].to;
if (!vis[v] && dy[v] == dx[u]+)
{
vis[v] = ;
if (cy[v]!=- && dis==dy[v])
continue;
if (cy[v]==- || dfs(cy[v]))
{
cy[v] = u;
cx[u] = v;
return ;
}
}
}
return ;
}
int Max_match ()
{//得到最大匹配数目
int res = ;
memset (cx, -, sizeof(cx));
//左边顶点i所匹配的右边的点
memset (cy, -, sizeof(cy));
//右边顶点i所匹配的左边的点
while (bfs ())
{
memset (vis, , sizeof(vis));
for (int i=; i<=n; i++)
if (cx[i] == -)
res += dfs(i);
}
return res;
}
int main ()
{
int cas, t, l = ;
scanf ("%d", &cas);
while (cas --)
{
scanf ("%d %d", &t, &n);
for (int i=; i<=n; i++)
{
scanf ("%lf %lf %lf", &p_gue[i].x, &p_gue[i].y, &p_gue[i].num);
p_gue[i].num *= t;
} scanf ("%d", &m);
for (int i=; i<=m; i++)
scanf ("%lf %lf", &p_umb[i].x, &p_umb[i].y); memset (head, -, sizeof(head));
tot = ;
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
{
double x = p_gue[i].x - p_umb[j].x;
double y = p_gue[i].y - p_umb[j].y;
double num = sqrt (x*x + y*y);
if (num <= p_gue[i].num)
Add (i, j);
}
printf ("Scenario #%d:\n%d\n\n", ++l, Max_match());
}
return ;
}