题意：有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 ;
}