POJ2239哈希取址+二分匹配

作者： | 来源：互联网 | 2023-09-17 13:45

B- SelectingCoursesTimeLimit:1000MS MemoryLimit:65536KB 64bitIOFormat:%I64d&%I

B - Selecting Courses

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d
& %I64u

Submit Status

Description

It is well known that it is not easy to select courses in the college, for there is usually conflict among the time of the courses. Li Ming is a student who loves study every much, and at the beginning of each term, he always wants to select courses as more
as possible. Of course there should be no conflict among the courses he selects.
There are 12 classes every day, and 7 days every week. There are hundreds of courses in the college, and teaching a course needs one class each week. To give students more convenience, though teaching a course needs only one class, a course will be taught several
times in a week. For example, a course may be taught both at the 7-th class on Tuesday and 12-th class on Wednesday, you should assume that there is no difference between the two classes, and that students can select any class to go. At the different weeks,
a student can even go to different class as his wish. Because there are so many courses in the college, selecting courses is not an easy job for Li Ming. As his good friends, can you help him?

Input

The input contains several cases. For each case, the first line contains an integer n (1 <= n <= 300), the number of courses in Li Ming‘s college. The following n lines represent n different courses. In each line, the first number is an integer t (1 <= t <=
7*12), the different time when students can go to study the course. Then come t pairs of integers p (1 <= p <= 7) and q (1 <= q <= 12), which mean that the course will be taught at the q-th class on the p-th day of a week.

Output

For each test case, output one integer, which is the maximum number of courses Li Ming can select.

Sample Input

5
1 1 1
2 1 1 2 2
1 2 2
2 3 2 3 3
1 3 3

Sample Output

这题刚开始理解题目错了，&＃23612;玛，看到样例中1 1有几个，所以还以为是重复的呢，就只取了一个，然后就剩下（1，1），（2，2），（3，2），（3，3），然后就得出样例答案为4.。直接WA一发，然后又重新读题才发现理解错题意了，晕……

题意原来是当前课程会在那些时间上几次课，刚开始因为当前是一个结点了，然后周数与节数又有两个数据，所以想想这两个如果要想放在图论中，那么当然得把这两个数据合成一个地址……哈哈这么想着就有思路了……因为以前做过哈希方面的题，所以保存了好多哈希取址的计算函数，在实际中用得最多最高效也是最容易的就是BKDRHash哈希函数了，其计算式为：a*131&＃43;b这个就作为一个新地址存下来，也就是另一个结点……因为这个计算式已经被好多人证实过了，对于全部的（a,b），其取唯一地址的函数可以用这个计算，这个函数在实际中也是证明被用得最多的了，当然这个没有处理地址冲突，所以地址还是有bug的，但是就这水题这个式子够了……

然后有了这两个结点当然就可以做边了，匹配就是二分匹配了……

哈希不懂的可以看我的另一篇博文：http://blog.csdn.net/u011466175/article/details/17484687

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 100010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
vectorv[MN];
int vis[MN],pre[MN];
int dfs(int u)
{
for(int i=0; i {
int j=v[u][i];
if(!vis[j])
{
vis[j]=1;
if(!pre[j]||dfs(pre[j]))
{
pre[j]=u;
return 1;
}
}
}
return 0;
}
int solve(int n)
{
int ans=0;
for(int i=1; i<=n; i++)
{
mem(vis,0);
ans+=dfs(i);
}
return ans;
}
int main()
{
int n,m,i,j,p,q;
while(~sca(n))
{
for(i=0;i<=n;i++) v[i].clear();
mem(pre,0);
for(i=1;i<=n;i++)
{
sca(m);
while(m--)
{
scanf("%d%d",&p,&q);
int cnt=p*131+q;//BKDRHash哈希取址计算式即可
v[i].push_back(cnt);
}
}
pri(solve(n));
}
return 0;
}

POJ 2239 哈希取址+二分匹配,布布扣,bubuko.com

推荐阅读

format
C语言初学者指南：利用二维数组与结构体实现贪食蛇游戏

本文面向非计算机专业背景的编程爱好者，介绍如何仅使用基础的C语言知识——二维数组和结构体，无需掌握复杂的数据结构如链表，即可编写一款经典的贪食蛇游戏。通过本教程，您将了解游戏开发的基本原理和实现方法。 ... [详细]

蜡笔小新 2024-11-27 18:05:55
list
MVC框架下使用DataGrid实现时间筛选与枚举填充

本文介绍如何在ASP.NET MVC项目中利用DataGrid组件增强搜索功能，具体包括使用jQuery UI的DatePicker插件添加时间筛选条件，并通过枚举数据填充下拉列表。 ... [详细]

蜡笔小新 2024-11-27 11:02:33
copy
深入解析Android Activity生命周期

本文详细探讨了Android中Activity的生命周期，通过实例代码和详细的步骤说明，帮助开发者更好地理解和掌握Activity各个阶段的行为。 ... [详细]

蜡笔小新 2024-11-27 03:28:32
list
Lua脚本深入解析：元表与元方法的应用

本文探讨了Lua中元表和元方法的使用，通过具体的代码示例展示了如何利用这些特性来实现类似C语言中的运算符重载功能。 ... [详细]

蜡笔小新 2024-11-27 19:31:10
list
拖拉切割直线

拖拉切割直线 ... [详细]

蜡笔小新 2024-11-27 19:20:38
list
四月个人任务：Linux基础操作与网络管理

本文介绍了两项主要任务：编写一个脚本来检测192.168.1.0/24子网中当前在线的IP地址，以及如何在Linux系统中挂载Windows网络共享目录。通过具体步骤和代码示例，帮助读者理解和掌握相关技能。 ... [详细]

蜡笔小新 2024-11-27 19:13:58
java
Python中调用Java代码的方法与实践

本文探讨了如何在Python环境中集成并调用Java代码，通过具体的步骤和示例展示了这一过程的技术细节。适合对跨语言编程感兴趣的开发者阅读。 ... [详细]

蜡笔小新 2024-11-27 17:54:57
java
代码生成器实战教程：提升编程效率的利器

本系列文章旨在通过一系列实践案例，详细介绍如何利用代码生成器提高开发效率。本文将引导您完成从下载安装到实际应用的全过程。 ... [详细]

蜡笔小新 2024-11-27 12:05:48
io
Python全栈之旅：SQLAlchemy ORM中的外键与关系

本文探讨了SQLAlchemy ORM框架中如何利用外键和关系（relationship）来建立表间联系，简化复杂的查询操作。通过示例代码详细解释了relationship的定义、使用方法及其与外键的相互作用。 ... [详细]

蜡笔小新 2024-11-27 11:20:01
search
探索HTML5：十五个关键的新特性

本文深入探讨了HTML5中十五个重要的新特性，为开发者提供了详细的指南。 ... [详细]

蜡笔小新 2024-11-26 19:09:22
list
BeautifulSoup4：Python的HTML/XML解析利器

BeautifulSoup4 是一个功能强大的HTML和XML解析库，它能够帮助开发者轻松地从网页中提取信息。本文将介绍BeautifulSoup4的基本功能、安装方法、与其他解析工具的对比以及简单的使用示例。 ... [详细]

蜡笔小新 2024-11-26 14:44:14
io
如何实现类似CSDN博客的页面返回顶部功能

本文将详细介绍如何实现类似于CSDN博客的页面返回顶部功能，通过调整返回速度和图标显示条件，使用户体验更加流畅。适合前端开发者参考学习。 ... [详细]

蜡笔小新 2024-11-27 18:22:17
io
VS Code 中 .vscode 文件夹配置详解

本文介绍了 VS Code 中 .vscode 文件夹下的配置文件及其作用，包括常用的预定义变量和三个关键配置文件：launch.json、tasks.json 和 c_cpp_properties.json。 ... [详细]

蜡笔小新 2024-11-27 17:52:29
window
如何在Android Studio中移除Activity的标题栏

本文介绍了在Android Studio中通过代码和配置文件两种方法来移除Activity的标题栏，并讨论了当Activity继承自AppCompatActivity时的特殊处理方法。 ... [详细]

蜡笔小新 2024-11-27 17:40:30
io
抽象工厂模式 c++

抽象工厂模式包含如下角色：AbstractFactory：抽象工厂ConcreteFactory：具体工厂AbstractProduct：抽象产品Product：具体产品https ... [详细]

蜡笔小新 2024-11-27 13:21:30

Tags | 热门标签

RankList | 热门文章