二分图（H-K算法）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int maxn=3000+100;
int head[maxn];
int mx[maxn],my[maxn];
int dx[maxn],dy[maxn];
int used[maxn];
struct Node{
   int x,y;
   int  s;
}e[maxn];
struct node{
   int x,y;
}pos[maxn];
struct edge{
    int u,v;
    int next;
}ee[maxn*maxn];
int cas,t,n,m,cnt,num,dis;
bool SearchP()
{
    queue<int>q;
    dis=0x3f3f3f3f;
    CLEAR(dx,-1);
    CLEAR(dy,-1);
    REPF(i,1,n)
      if(mx[i]==-1)
      {
          q.push(i);
          dx[i]=0;
      }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(dx[u]>dis) break;
        for(int i=head[u];i!=-1;i=ee[i].next)
        {
            int v=ee[i].v;
            if(dy[v]==-1)
            {
                dy[v]=dx[u]+1;
                if(my[v]==-1)  dis=dy[v];
                else
                {
                    dx[my[v]]=dy[v]+1;
                    q.push(my[v]);
                }
            }
        }
    }
    return dis!=0x3f3f3f3f;
}
bool dfs(int u)
{
    for(int i=head[u];i!=-1;i=ee[i].next)
    {
        int v=ee[i].v;
        if(!used[v]&&dy[v]==dx[u]+1)
        {
            used[v]=1;
            if(my[v]!=-1&&dy[v]==dis)  continue;
            if(my[v]==-1||dfs(my[v]))
            {
                my[v]=u;
                mx[u]=v;
                return true;
            }
        }
    }
    return  false;
}
void work()
{
    int res=0;
    CLEAR(mx,-1);
    CLEAR(my,-1);
    while(SearchP())
    {
        CLEAR(used,0);
        REPF(i,1,n)
          if(mx[i]==-1&&dfs(i))  res++;
    }
    printf("Scenario #%d:\n%d\n\n",++num,res);
}
bool ok(int i,int j)
{
    double d=sqrt((double)(e[i].x-pos[j].x)*(e[i].x-pos[j].x)+(double)(e[i].y-pos[j].y)*(e[i].y-pos[j].y));
    return d/e[i].s<=t;
}
void addedge(int u,int v)
{
    ee[cnt].u=u;ee[cnt].v=v;
    ee[cnt].next=head[u];
    head[u]=cnt++;
}
int main()
{
    int x,y,w;
    num=0;
    scanf("%d",&cas);
    while(cas--)
    {
        CLEAR(head,-1);cnt=0;
        scanf("%d%d",&t,&n);
        REPF(i,1,n)
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].s);
        scanf("%d",&m);
        REPF(i,1,m)
        {
            scanf("%d%d",&pos[i].x,&pos[i].y);
            REPF(j,1,n)
                if(ok(j,i))  addedge(j,i);
        }
        work();
    }
    return 0;
}