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

推荐阅读

jsp
LDAP服务器配置与管理

本文介绍如何通过安装和配置SSSD服务来统一管理用户账户信息，并实现其他系统的登录调用。通过图形化交互界面配置LDAP服务器，确保用户账户信息的集中管理和安全访问。 ... [详细]

蜡笔小新 2024-11-13 18:19:52
default
SoundPool

如果应用程序经常播放密集、急促而又短暂的音效（如游戏音效）那么使用MediaPlayer显得有些不太适合了。因为MediaPlayer存在如下缺点：1)延时时间较长，且资源占用率高 ... [详细]

蜡笔小新 2024-11-13 16:47:19
jsp
[c++基础]STL

cppfig15_10.cppincludeincludeusingnamespacestd;templatevoidprintVector(constvector&integer ... [详细]

蜡笔小新 2024-11-13 13:22:43
web
Python 数据可视化实战指南

本文详细介绍如何使用 Python 进行数据可视化，涵盖从环境搭建到具体实例的全过程。 ... [详细]

蜡笔小新 2024-11-13 06:03:30
jsp
Pythonmysql数据库

importpymysql#一、直接连接mysql数据库'''coonpymysql.connect(host'192.168.*.*',u ... [详细]

蜡笔小新 2024-11-12 16:51:59
dll
c/c++常用代码doc,ppt,xls文件格式转PDF格式[转]

[转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]

蜡笔小新 2024-11-12 16:19:40
web
Framework7：构建跨平台移动应用的高效框架

Framework7 是一个开源免费的框架，适用于开发混合移动应用（原生与HTML混合）或iOS&Android风格的Web应用。此外，它还可以作为原型开发工具，帮助开发者快速创建应用原型。 ... [详细]

蜡笔小新 2024-11-12 14:47:56
sum
解决Bootstrap DataTable Ajax请求重复问题

在最近的一个项目中，我们使用了JQuery DataTable进行数据展示，虽然使用起来非常方便，但在测试过程中发现了一个问题：当查询条件改变时，有时查询结果的数据不正确。通过FireBug调试发现，点击搜索按钮时，会发送两次Ajax请求，一次是原条件的请求，一次是新条件的请求。 ... [详细]

蜡笔小新 2024-11-12 13:59:27
dll
开机自启动的几种方式

0x01快速自启动目录快速启动目录自启动方式源于Windows中的一个目录，这个目录一般叫启动或者Startup。位于该目录下的PE文件会在开机后进行自启动 ... [详细]

蜡笔小新 2024-11-12 11:16:30
window
解决 MySQL 无法连接到 localhost 的错误 2003 (HY000)

本文旨在解决 MySQL 无法连接到 localhost 的常见问题，并提供详细的步骤来确保 MySQL 服务正确启动和配置。 ... [详细]

蜡笔小新 2024-11-13 17:59:18
sum
单片微机原理P3：80C51外部拓展系统

　　外部拓展其实是个相对来说很好玩的章节，可以真正开始用单片机写程序了，比较重要的是外部存储器拓展，81C55拓展，矩阵键盘，动态显示，DAC和ADC。0.IO接口电路概念与存 ... [详细]

蜡笔小新 2024-11-12 19:51:29
version
深入解析数据库并发控制机制

本文详细介绍了数据库并发控制的基本概念、重要性和具体实现方法。并发控制是确保多个事务在同时操作数据库时保持数据一致性的关键机制。文章涵盖了锁机制、多版本并发控制（MVCC）、乐观并发控制和悲观并发控制等内容。 ... [详细]

蜡笔小新 2024-11-12 12:37:08
web
php更新数据库字段的函数是,php更新数据库字段的函数是

php更新数据库字段的函数是,php更新数据库字段的函数是 ... [详细]

蜡笔小新 2024-11-12 11:37:31
runtime
Go (Golang) 语言Golang 定时器Timer和Ticker、time.AfterFunc、time.NewTicker()实例

文章目录Golang定时器Timer和Tickertime.Timertime.NewTimer()实例time.AfterFunctime.Tickertime.NewTicke ... [详细]

蜡笔小新 2024-11-12 09:39:10
jsp
第二十五天接口、多态

1.java是面向对象的语言。设计模式：接口接口类是从java里衍生出来的，不是python原生支持的主要用于继承里多继承抽象类是python原生支持的主要用于继承里的单继承但是接 ... [详细]

蜡笔小新 2024-11-12 06:43:20

Tags | 热门标签

RankList | 热门文章