题目名称 1199. 选课
输入输出 course.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-10-22
开放分组 全部用户
提交状态
分类标签
通过:79, 提交:198, 通过率:39.9%
Gravatardateri 100 0.000 s C++
GravatarYoungsc 100 0.013 s C++
GravatarAglove 100 0.017 s C++
Gravatarluo 100 0.021 s C++
Gravatartingtime 100 0.025 s C++
GravatarXGY 100 0.027 s C++
GravatarXGY 100 0.033 s C++
Gravatartingtime 100 0.034 s C++
GravatarHydrochloric 100 0.049 s C++
Gravatartingtime 100 0.055 s C++
关于 选课 的讨论
這題一開始看著很像TopoSort
GravatarMakazeu
2012-10-22 20:55 1楼
樹形DP,用VECTOR記錄路徑就一次 誒西 了
GravatarMakazeu
2012-10-22 21:37 2楼
此題乃Vijos 1180[選課]一體的增強版。
http://vijos.org/Problem_Show.asp?id=1180
GravatarMakazeu
2012-10-22 22:59 3楼
速度是硬伤,AT,你怎么看?
GravatarTruth.Cirno
2012-10-23 07:42 4楼
vector無壓力 いいえ圧力ません
GravatarMakazeu
2012-10-23 08:38 5楼
第一问非常简单,但是第二问把我卡住了,各位大牛能教教我如何输出方案吗?
Gravatarlqwang1985
2014-09-23 02:46 6楼
Gravatarassassain
2015-06-11 17:26 7楼
Gravatarzys
2015-10-24 08:01 8楼
这难度才一星,都快写死我了。
GravatarMagic_Sheep
2016-02-19 17:05 9楼
竟然排了趟序。。。
Gravatarliu_runda
2016-04-27 11:33 10楼
路径输出……
Gravatar水墨青花
2016-04-30 11:04 11楼
回复 @Ezoi_Magic_Sheep :
曾经的YMY大爷...被79行的代码险些写死...如今的YMY大爷,随手一写790行 Orz
Gravatar沉迷学习的假的Keller
2016-10-04 19:50 12楼
就这么...a了?我以为会t成狗。。。
GravatarHyoi_Turkey
2017-09-21 09:52 13楼

1199. 选课

★★☆   输入文件:course.in   输出文件:course.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

大学里实行学分。每门课程都有一定的学分,学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。
每个学生都要选择规定数量的课程。其中有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如,《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号,课号依次为1,2,3,……。下面举例说明

上例中1是2的先修课,即如果要选修2,则1必定已被选过。同样,如果要选修3,那么1和2都一定已被选修过。
学生不可能学完大学所开设的所有课程,因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案,使得你能得到学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

【输入格式】

第一行包括两个正整数M、N(中间用一个空格隔开)其中M表示待选课程总数(1≤M≤500),N表示学生可以选的课程总数(1≤N≤M)。
以下M行每行代表一门课,课号依次为1,2,…,M。每行有两个数(用一个空格隔开),第一个数为这门课的先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。

【输出格式】

第一行只有一个数,即实际所选课程的学分总数。以下N行每行有一个数,表示学生所选课程的课号。

【样例输入】

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

【样例输出】

13
2
3
6
7

【提示】

最后结果按学生所选课程课号的升序输出。

【来源】