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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费