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

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

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.