首页    技术博客    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


推荐阅读
  • replace

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

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

    次小生成树问题的高效求解

    本文探讨了如何通过最小生成树（MST）来计算严格次小生成树。在处理过程中，需特别注意所有边权重相等的情况，以避免错误。我们首先构建最小生成树，然后枚举每条非树边，检查其是否能形成更优的次小生成树。 ... [详细]
  • tree

    QUIC协议：快速UDP互联网连接

    QUIC协议：快速UDP互联网连接
    QUIC（Quick UDP Internet Connections）是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP，并结合了TLS级别的安全性，提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • tree

    深入理解OAuth认证机制

    深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准，旨在为第三方应用提供安全的用户资源访问授权，同时确保用户的账户信息（如用户名和密码）不会暴露给第三方。 ... [详细]
  • tree

    国内BI工具迎战国际巨头Tableau，稳步崛起

    国内BI工具迎战国际巨头Tableau，稳步崛起
    尽管商业智能（BI）工具在中国的普及程度尚不及国际市场，但近年来，随着本土企业的持续创新和市场推广，国内主流BI工具正逐渐崭露头角。面对国际品牌如Tableau的强大竞争，国内BI工具通过不断优化产品和技术，赢得了越来越多用户的认可。 ... [详细]
  • tree

    2018回顾与2019展望

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

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

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

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

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

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

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

    通过类型和标签选择元素

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

    新浪笔试题

    1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • text

    深入理解Cookie与Session会话管理

    深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]
  • command

    Xcode 中多行代码缩进技巧

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

    Linux 自动化安装脚本详解

    本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建，还处理了系统服务的配置和启动，确保在多种 Linux 发行版上都能顺利运行。 ... [详细]
  • ip

    在Linux系统中配置并启动ActiveMQ

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