HDU2389 Rain on your Parade —— 二分图最大匹配 HK算法

2023-10-13 22:10

本文主要是介绍HDU2389 Rain on your Parade —— 二分图最大匹配 HK算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:https://vjudge.net/problem/HDU-2389

 

Rain on your Parade

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 655350/165535 K (Java/Others)
Total Submission(s): 4889    Accepted Submission(s): 1612


Problem Description
You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour? 

Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however. 

 

Input
The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= s i <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.

 

Output
For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.

 

Sample Input
2 1 2 1 0 3 3 0 3 2 4 0 6 0 1 2 1 1 2 3 3 2 2 2 2 4 4

 

Sample Output
Scenario #1: 2 Scenario #2: 2

 

Source
HDU 2008-10 Public Contest

 

Recommend
lcy

 

 

题解:

就直接求二分图最大匹配,不过由于数据较大,匈牙利算法超时,所以需要用HK算法。

 

 

代码如下:

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <vector>
  7 #include <map>
  8 #include <set>
  9 #include <queue>
 10 #include <sstream>
 11 #include <algorithm>
 12 using namespace std;
 13 const int INF = 2e9;
 14 const int MOD = 1e9+7;
 15 const int MAXN = 3000+10;
 16 
 17 struct Node
 18 {
 19     int x, y, speed;
 20 }gue[MAXN], umb[MAXN];
 21 
 22 int uN, vN, t;
 23 vector<int>g[MAXN];
 24 
 25 int Mx[MAXN], My[MAXN];
 26 int dx[MAXN], dy[MAXN];
 27 int dis;
 28 bool used[MAXN];
 29 
 30 bool SearchP()
 31 {
 32     queue<int>Q;
 33     dis = INF;
 34     memset(dx, -1, sizeof(dx));
 35     memset(dy, -1, sizeof(dy));
 36     for(int i = 1; i<=uN; i++)
 37     if(Mx[i]==-1)
 38     {
 39         Q.push(i);
 40         dx[i] = 0;
 41     }
 42 
 43     while(!Q.empty())
 44     {
 45         int u = Q.front();
 46         Q.pop();
 47         if(dx[u]>dis) break;
 48         int sz = g[u].size();
 49         for(int i = 0; i<sz; i++)
 50         {
 51             int v = g[u][i];
 52             if(dy[v]==-1)
 53             {
 54                 dy[v] = dx[u] + 1;
 55                 if(My[v]==-1) dis = dy[v];
 56                 else
 57                 {
 58                     dx[My[v]] = dy[v] + 1;
 59                     Q.push(My[v]);
 60                 }
 61             }
 62         }
 63     }
 64     return dis!=INF;
 65 }
 66 
 67 bool DFS(int u)
 68 {
 69     int sz = g[u].size();
 70     for(int i = 0; i<sz; i++)
 71     {
 72         int v = g[u][i];
 73         if(!used[v] && dy[v]==dx[u]+1)
 74         {
 75             used[v] = true;
 76             if(My[v]!=-1 && dy[v]==dis) continue;
 77             if(My[v]==-1 || DFS(My[v]))
 78             {
 79                 My[v] = u;
 80                 Mx[u] = v;
 81                 return true;
 82             }
 83         }
 84     }
 85     return false;
 86 }
 87 
 88 int MaxMatch()
 89 {
 90     int res = 0;
 91     memset(Mx, -1, sizeof(Mx));
 92     memset(My, -1, sizeof(My));
 93     while(SearchP())
 94     {
 95         memset(used, false, sizeof(used));
 96         for(int i = 1; i<=uN; i++)
 97             if(Mx[i]==-1 && DFS(i))
 98                 res++;
 99     }
100     return res;
101 }
102 
103 int main()
104 {
105     int T, kase = 0;
106     scanf("%d", &T);
107     while(T--)
108     {
109         scanf("%d%d", &t, &uN);
110         for(int i = 1; i<=uN; i++)
111         {
112             scanf("%d%d%d", &gue[i].x, &gue[i].y, &gue[i].speed);
113             g[i].clear();
114         }
115 
116         scanf("%d", &vN);
117         for(int i = 1; i<=vN; i++)
118             scanf("%d%d", &umb[i].x, &umb[i].y);
119 
120         for(int i = 1; i<=uN; i++)
121         for(int j = 1; j<=vN; j++)
122         {
123             int dis = (gue[i].x-umb[j].x)*(gue[i].x-umb[j].x)
124                       +(gue[i].y-umb[j].y)*(gue[i].y-umb[j].y);
125             int s = gue[i].speed*gue[i].speed*t*t;
126             if(s>=dis) g[i].push_back(j);
127         }
128 
129         int ans = MaxMatch();
130         printf("Scenario #%d:\n%d\n\n", ++kase, ans);
131 
132     }
133 }
View Code

 

转载于:https://www.cnblogs.com/DOLFAMINGO/p/7818293.html

这篇关于HDU2389 Rain on your Parade —— 二分图最大匹配 HK算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/206179

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制