首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

4



这题刚开始理解题目错了，&＃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


推荐阅读
  • function

    深入理解 Oracle 存储函数：计算员工年收入

    深入理解 Oracle 存储函数：计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]
  • function

    移动 UI 设计基础：打造简洁高效的用户界面

    本章将深入探讨移动 UI 设计的核心原则，帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧，您将能够创建出既美观又实用的移动应用。 ... [详细]
  • function

    从JDE系统中提取完整字典数据

    本文介绍如何通过SQL查询从JDE（JD Edwards）系统中提取所有字典数据，涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • text

    使用 NSTimer 实现倒计时功能

    本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]
  • text

    2018回顾与2019展望

    本文总结了2018年的关键成就，包括职业变动、购车、考取驾照等重要事件，并分享了读书、工作、家庭和朋友方面的感悟。同时，展望2019年，制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • text

    四载相伴，与51CTO学院共成长

    在计算机技术的学习道路上，51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域，51CTO学院始终是我信赖的学习平台。 ... [详细]
  • text

    CSS 布局：液态三栏混合宽度布局

    CSS 布局：液态三栏混合宽度布局
    本文介绍了如何使用 CSS 实现液态的三栏布局，其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性，可以实现灵活且响应式的网页设计。 ... [详细]
  • install

    Linux 系统启动故障排除指南：MBR 和 GRUB 问题

    Linux 系统启动故障排除指南：MBR 和 GRUB 问题
    本文详细介绍了 Linux 系统启动过程中常见的 MBR 扇区和 GRUB 引导程序故障及其解决方案，涵盖从备份、模拟故障到恢复的具体步骤。 ... [详细]
  • install

    通过类型和标签选择元素

    本文介绍了如何使用jQuery根据元素的类型（如复选框）和标签名（如段落）来获取DOM对象。这有助于更高效地操作网页中的特定元素。 ... [详细]
  • install

    Xcode 中多行代码缩进技巧

    本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进，包括右缩进和左缩进的具体操作方法。 ... [详细]
  • install

    在Linux系统中配置并启动ActiveMQ

    在Linux系统中配置并启动ActiveMQ
    本文详细介绍了如何在Linux环境中安装和配置ActiveMQ，包括端口开放及防火墙设置。通过本文，您可以掌握完整的ActiveMQ部署流程，确保其在网络环境中正常运行。 ... [详细]
  • window

    使用Windows批处理脚本监控并重启Java应用程序

    本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序，确保其持续稳定运行。脚本每30分钟检查一次，并在需要时重启Java程序。同时，它会将任务结果发送到Redis。 ... [详细]
  • window

    MySQL中枚举类型的所有可能值获取方法

    MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举（ENUM）类型字段所有可能取值的方法，帮助开发者更好地理解和利用这一数据类型。 ... [详细]
  • window

    启动MySQL服务的命令行步骤

    本文详细介绍了如何通过命令行启动MySQL服务，包括打开命令提示符窗口、进入MySQL的bin目录、输入正确的连接命令以及注意事项。文中还提供了更多相关命令的资源链接。 ... [详细]
  • sum

    深入理解OAuth认证机制

    深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准，旨在为第三方应用提供安全的用户资源访问授权，同时确保用户的账户信息（如用户名和密码）不会暴露给第三方。 ... [详细]
author-avatar
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有