F - Rain on your Parade (HK)

2024-03-20 22:38
文章标签 parade rain hk

本文主要是介绍F - Rain on your Parade (HK),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

F - Rain on your Parade

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:
2Scenario #2:
2

题意:

        先给出距离下雨的时间,再给出n个人和m把雨伞的坐标位置,以及每个人的奔跑速度。每把雨伞只能供一人使用。求在下雨前最多有多少人可以拿到雨伞。

思路:

       二分匹配 + HK算法(看了很多博客,并没有看懂)

只有模板:http://www.cnblogs.com/kuangbin/archive/2011/08/12/2135898.html

注意: 

       1) 在判断客人是否能达到有伞的地方的函数——Pan(),要用double型。

       2)本代码从 1 开始。。。

代码:

  

#include<map>
#include<queue>
#include<math.h>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define MM 3005
const int INF=1e9;
int line[MM][MM],book[MM];
int mx[MM],my[MM],dx[MM],dy[MM],nx,ny,dis;
int t,gu,un;
struct zaq
{int x,y,s;
} g[MM],u[MM];
bool Pan(zaq A,zaq B)
{double ans;     //用double型ans=sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));if(ans<=t*A.s)return true;elsereturn false;
}
bool Search()
{queue<int>qu;dis=INF;mem(dx,0);mem(dy,0);for(int i=1; i<=nx; i++){if(!mx[i]){qu.push(i);dx[i]=0;}}while(!qu.empty()){int kk=qu.front();qu.pop();if(dx[kk]>dis)break;for(int v=1; v<=ny; v++){if(line[kk][v] && !dy[v]){dy[v]=dx[kk]+1;if(!my[v])dis=dy[v];else{dx[my[v]]=dy[v]+1;qu.push(my[v]);}}}}return dis != INF;
}
bool Find(int x)
{for(int v=1; v<=ny; v++){if(!book[v] && line[x][v] && dy[v]==dx[x]+1){book[v]=1;if(my[v] && dy[v]==dis)continue;if(!my[v] || Find(my[v])){my[v]=x;mx[x]=v;return true;}}}return false;
}
void match()
{int ans=0;mem(mx,0);mem(my,0);while(Search()){mem(book,0);for(int i=1; i<=nx; i++){if(!mx[i] && Find(i))ans++;}}printf("%d\n",ans);
}
int main()
{int ca,cas=1;scanf("%d",&ca);while(ca--){mem(line,0);scanf("%d",&t);scanf("%d",&gu);for(int i=1; i<=gu; i++)scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].s);scanf("%d",&un);for(int i=1; i<=un; i++)scanf("%d%d",&u[i].x,&u[i].y);for(int i=1; i<=gu; i++)for(int j=1; j<=un; j++)if(Pan(g[i],u[j]))line[i][j]=1;nx=gu;ny=un;printf("Scenario #%d:\n",cas++);match();printf("\n");}return 0;
}

 

 

这篇关于F - Rain on your Parade (HK)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

LeetCode - 42. Trapping Rain Water

42. Trapping Rain Water  Problem's Link  ---------------------------------------------------------------------------- Mean:  在坐标上给你一些竖直放置的条形积木,问你这个积木能够容纳多少液体. analyse: 首先找出最高的积木,然后从前往后一直

【HDU】2389 Rain on your Parade 二分匹配 Hopcroft-Krap算法

传送门:【HDU】2389 Rain on your Parade 题目分析: 这题目非要我学Hopcroft-Krap= =||。。普通的DFS版的二分匹配不行,最大流又爆内存。。不得不学更好的算法了。 二分匹配的其他性质我也不多说了,不会的自行搜索,网上很多的。 现在我主要对该算法的实现发表一下自己的见解。(算法复杂度的证明不会,论文没看太懂) 该算法的核心思想是通过bfs寻找

【二分匹配】【HK算法模板】

/**********************************************二分图匹配(Hopcroft-Carp的算法)。初始化:g[][]邻接矩阵调用:res=MaxMatch(); Nx,Ny要初始化!!!时间复杂大为 O(V^0.5 E)适用于数据较大的二分匹配 ***********************************************/

【LeetCode最详尽解答】42-接雨水 Trapping-Rain-Water

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家! 链接: 42-接雨水 直觉 通过可视化图形来解决这个问题会更容易理解和解决。 给定输入: height = [0,1,0,2,1,0,1,3,2,1

HDU-1150 HK二分图最小点覆盖

//二分图最小点覆盖 = 二分图最大匹配#include<stdio.h>#include<string.h>#include<queue>using namespace std;const int maxn = 105;const int inf = 1<<30;int nx,ny,m;int dis;int map[maxn][maxn];int cx[maxn],cy[m

leetcode-42. Trapping Rain Water

leetcode-42. Trapping Rain Water 题目: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For examp

hdu 4637 Rain on your Fat brother(几何+区间覆盖)

题目连接:hdu 4637 Rain on your Fat brother 解题思路 题目等价于求线段与雨水的交,t为mazi停下来的时间,妹子移动相对于雨水的移动路线为 (x,0)−(x−V1∗t,V∗t) (x,0)-(x-V1*t, V*t),然后求出线段与每个雨水相交点,计算出进出时间,注意于圆相交的部分只能计算下半圆。 接着做一下区间覆盖,因为雨滴有重叠。 代码 #inclu

Leetcode 042 Trapping Rain Water(高效)

题目连接:Leetcode 042 Trapping Rain Water 解题思路:从左向右遍历一遍,保存每个位置往左的最高值。再从右往左遍历一遍,保存每个位置往右的最高值。最后遍历一遍数组,取左右最高值中较小的一个,减去当前值,即为这个位置增加的量。 class Solution {public:int trap(vector<int>& height) {int n = height.s

HDU 3340 Rain in ACStar(线段树+几何)

HDU 3340 Rain in ACStar 题目链接 题意:给定几个多边形(3-5边形),然后中间有一些询问,询问一个区间的总面积 思路:多边形分割为梯形,梯形的面积为上底d1 + 下底d2 乘上 高度 / 2,两个梯形面积累加的话,可以等价为上底下底累加,所以就可以用线段树搞了,然后给定的多边形点是按顺序的,可以利用容斥去方便把一个询问拆分成几个询问 代码: #in

LeetCode 题解(14):Trapping Rain Water

题目: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,