主题链接:
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;
}
版权声明:本文博主原创文章,博客,未经同意不得转载。
POJ2239 Selecting Courses【二部图最大匹配】的更多相关文章
-
poj2239 Selecting Courses --- 二分图最大匹配
匈牙利算法模板题 有n门课程,每门课程可能有不同一时候间,不同一时候间的课程等价. 问不冲突的情况下最多能选多少门课. 建立二分图,一边顶点表示不同课程,还有一边表示课程的时间(hash一下). #i ...
-
POJ-2239 Selecting Courses,三维邻接矩阵实现,钻数据空子。
Selecting Courses Time Limit: 1000MS Memory Limit: 65536K Description It is well known that ...
-
POJ2239 Selecting Courses(二分图最大匹配)
题目链接 N节课,每节课在一个星期中的某一节,求最多能选几节课 好吧,想了半天没想出来,最后看了题解是二分图最大匹配,好弱 建图: 每节课 与 时间有一条边 #include <iostream ...
-
[POJ] 2239 Selecting Courses(二分图最大匹配)
题目地址:http://poj.org/problem?id=2239 Li Ming大学选课,每天12节课,每周7天,每种同样的课可能有多节分布在不同天的不同节.问Li Ming最多可以选多少节课. ...
-
poj 2239 Selecting Courses (二分匹配)
Selecting Courses Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8316 Accepted: 3687 ...
-
HDU 3697 Selecting courses(贪心)
题目链接:pid=3697" target="_blank">http://acm.hdu.edu.cn/showproblem.php?pid=3697 Prob ...
-
POJ2239_Selecting Courses(二分图最大匹配)
解题报告 http://blog.csdn.net/juncoder/article/details/38154699 题目传送门 题意: 每天有12节课.一周上7天,一门课在一周有多天上课. 求一周 ...
-
hdu 3697 10 福州 现场 H - Selecting courses 贪心 难度:0
Description A new Semester is coming and students are troubling for selecting courses. Students ...
-
HDU 3697 Selecting courses(贪心+暴力)(2010 Asia Fuzhou Regional Contest)
Description A new Semester is coming and students are troubling for selecting courses. Students ...
随机推荐
-
BAT command
http://www.cnblogs.com/SunShineYPH/archive/2011/12/13/2285570.html BAT常用命令 1.@ 它的作用是隐藏它后面这一行的命令本身(只能 ...
-
linux下查看某软件是否已安装, ubuntu安装deb包
1.rpm包安装的,可以用rpm -qa看到,如果要查找某软件包是否安装,用 rpm -qa | grep “软件或者包的名字”. [root@hexuweb102 ~] rpm -qa | grep ...
-
c# 常用正则
"^\d+$" //非负整数(正整数 + 0) "^[0-9]*[1-9][0-9]*$" //正整数 "^((-\d+)|(0+))$" ...
-
腾讯视频嵌入手机端网站demo - 就像微信文章中一样一样的
页面中的调用如下: <iframe id="video_iframe" class="video_iframe" src="TenVideoPl ...
-
spoj 2319 BIGSEQ - Sequence
You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partitio ...
-
关于ECSHOP模板架设的服务器php版本过高报错的解决方法(二)
ECShop安装之后,在后台发现一个错误,这个错误提示的意思:mktime()方法不带参数被调用时,会被抛出一个报错提示. ECShop安装之后,在后台发现一个错误提示: Strict Standar ...
-
CountDownLatch, CyclicBarrier and Semaphore
Reference: [1] http://shazsterblog.blogspot.co.uk/2011/12/comparison-of-countdownlatch.html CountDow ...
- tomcat配置之后,localhost:8080访问不到猫界面解决办法
-
Netty Nio启动全流程
Netty Nio启动全流程 1. 各组件之间的关系 说明:EventLoopGroup类似线程池,EventLoop为单线程,每个EventLoop关联一个Nio Selector,用于注册Chan ...
-
[原创]关于在VS解决方案下使用文件夹管理多个项目层次关系的说明
由于所创建的应用项目或类库项目较多,于是将这些类库放到一个文件夹下.在VS解决方案下确实能看到一个文件夹下多个类库项目这种层次关系.如下图所示: 但打开“我的电脑”,看到的只有类库,并未看到维护层次关 ...