Hdu 3289 Rain on your Parade (二分图匹配 Hopcroft-Karp)

题目链接：

　　Hdu 3289 Rain on your Parade

题目描述：
　　有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 ;

 }