POJ2239 Selecting Courses【二部图最大匹配】

POJ2239 Selecting Courses【二部图最大匹配】

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

主题链接:

http://poj.org/problem?id=2239


题目大意:

学校总共同拥有N门课程,而且学校规定每天上12节可,一周上7天。

给你每门课每周上的次数,和哪一天哪一节

上的。假设有多门课程在同一天同一节课上。那么你仅仅能选择当中一门。那么问题来了:最多能同一时候选多少

门课而不发生冲突呢。


输入说明:

先给你一个N。表示有N门课。接下来N行,每行第一个数字x,表示这门课每周上几节。接下来是x对数。第

一个数D表示是这一周哪一天上的,第二个数C表示是这一天哪一节课上的。


思路:

将这道题来看做二分图匹配问题。

建立一个二分图,一边代表课程,一边代表某一节课(将一周7*12节课按

1~7*12来排列)。将课程和该课程上的某一节课相应建边,再求这个二分图的最大匹配数就可以。这里用匈牙

利DFS版来做。


AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 330;

int Map[MAXN][MAXN];
int Mask[MAXN];
int N,M;
int cx[MAXN],cy[MAXN];

int FindPath(int u)
{
    for(int i = 1; i <= M; ++i)
    {
        if(Map[u][i] && !Mask[i])
        {
            Mask[i] = 1;
            if(cy[i] == -1 || FindPath(cy[i]))
            {
                cy[i] = u;
                cx[u] = i;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    int res = 0;
    for(int i = 1; i <= N; ++i)
        cx[i] = -1;
    for(int i = 1; i <= M; ++i)
        cy[i] = -1;

    for(int i = 1; i <= N; ++i)
    {
        if(cx[i] == -1)
        {
            for(int j = 1; j <= M; ++j)
                Mask[j] = 0;
            res += FindPath(i);
        }
    }
    return res;
}

int main()
{
    int a,b,id;
    while(~scanf("%d",&N))
    {
        memset(Map,false,sizeof(Map));
        M = 7*12;

        for(int i = 1; i <= N; ++i)
        {
            scanf("%d",&id);
            for(int j = 1; j <= id; ++j)
            {
                scanf("%d%d",&a,&b);
                Map[i][(a-1)*12+b] = 1;
            }
        }
        printf("%d\n",MaxMatch());
    }

    return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/116838.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • java有全局变量吗_java局部变量和成员变量的区别

    java有全局变量吗_java局部变量和成员变量的区别//    java全局变量危害 //    最近为了图快捷,使用了全局变量,然后就想到了一些危害//  1.线程不安全:线程中多个全局变量,修改容易冲突,需要加锁//  2.增加耦合性:修改全局变量可能会影响其他模块//  3.难以定位修改:难以定位全局变量在哪里被修改了,加大了调用难度//  4.长期占用内存:生命

    2022年8月21日
    3
  • pyttsx3 快速上手之:语音合成播报

    pyttsx3 快速上手之:语音合成播报Pythonpyttsx3使用之:语音播报pyttsx3是python中最常用的文字转语音库,使用方便,功能较为完整首先安装pyttsx3lib:pipinstallpyttsx3然后封装下API,实现为speaker.py:importpyttsx3global__speak_engine__speak_engine=Nonedefsay(content): global__speak_engine ifnot__speak_engine:

    2022年6月26日
    57
  • 创业公司聘请的第一个雇员值得注意 6 事

    创业公司聘请的第一个雇员值得注意 6 事

    2022年1月5日
    42
  • 公平锁与非公平锁_公平锁和非公平锁区别

    公平锁与非公平锁_公平锁和非公平锁区别公平锁和非公平锁一、如果一个锁是公平的,那么获取的顺序就应该符合请求的绝对顺序,即FIFO。二、测试结果 非公平性锁可能使线程“饥饿”,为什么它又被设定成默认的实现呢?再次观察上表的结果,如果把每次不同线程获取到锁定义为1次切换,公平性锁在测试中进行了10次切换,而非公平性锁只有5次切换,这说明非公平性锁的开销更小。三、,公平性锁保证了锁的获取按照FIFO原则,而代价是进行…

    2022年8月12日
    6
  • Stimulsoft 仪表板.JS 2022.2.1

    Stimulsoft 仪表板.JS 2022.2.1Stimulsoft仪表板.JS2022.2.1  二维码视觉设计-使用组件编辑器中的属性定义各种图形元素的颜色和形状。  仪表板的新交互式按钮组件-允许您使用脚本平台语言或Blockly执行脚本。它包括几个可视化设置,这些设置取决于按钮的状态。  仪表板的新卡片组件-此分析组件允许您将数据分组、处理和显示为仪表板中的卡片。它支持所有类型的图形表示,包括集群列、色标、指标、气泡和迷你图。它能够显示文本、数值和图像。  仪表板的新图形堆叠图表类型-此图表用于显示值在整体指标中的

    2022年7月26日
    3
  • idea设置默认maven路径_idea查看maven路径

    idea设置默认maven路径_idea查看maven路径在idea中每次创建maven都要调整位置是不是很烦~可以通过一下方式设置maven默认配置不仅仅对maven有效,其他默认属性同样管用方法介绍:File->OtherSettings->SettingsforNewProject①②开始设置…

    2022年9月1日
    2

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号