首页 > 代码库 > 2014多校9(1007)hdu4966(最小树形图)
2014多校9(1007)hdu4966(最小树形图)
GGS-DDU
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 324 Accepted Submission(s): 171
Problem Description
Do you think this is a strange problem name? That is because you don‘t know its full name---‘Good Good Study and Day Day Up!". Very famous sentence! Isn‘t it?
Now "GGS-DDU" is lzqxh‘s target! He has N courses and every course is divided into a plurality of levels. Just like College English have Level 4 and Level 6.
To simplify the problem, we suppose that the i-th course has Levels from level 0 to level a[i]. And at the beginning, lzqxh is at Level 0 of every course. Because his target is "GGS-DDU", lzqxh wants to reach the highest Level of every course.
Fortunately, there are M tutorial classes. The i-th tutoial class requires that students must reach at least Level L1[i] of course c[i] before class begins. And after finishing the i-th tutorial class, the students will reach Level L2[i] of course d[i]. The i-th tutoial class costs lzqxh money[i].
For example, there is a tutorial class only students who reach at least Level 5 of "Tiyu" can apply. And after finishing this class, the student‘s "MeiShu" will reach Level 10 if his "MeiShu"‘s Level is lower than 10. (Don‘t ask me why! Supernatural class!!!")
Now you task is to help lzqxh to compute the minimum cost!
Now "GGS-DDU" is lzqxh‘s target! He has N courses and every course is divided into a plurality of levels. Just like College English have Level 4 and Level 6.
To simplify the problem, we suppose that the i-th course has Levels from level 0 to level a[i]. And at the beginning, lzqxh is at Level 0 of every course. Because his target is "GGS-DDU", lzqxh wants to reach the highest Level of every course.
Fortunately, there are M tutorial classes. The i-th tutoial class requires that students must reach at least Level L1[i] of course c[i] before class begins. And after finishing the i-th tutorial class, the students will reach Level L2[i] of course d[i]. The i-th tutoial class costs lzqxh money[i].
For example, there is a tutorial class only students who reach at least Level 5 of "Tiyu" can apply. And after finishing this class, the student‘s "MeiShu" will reach Level 10 if his "MeiShu"‘s Level is lower than 10. (Don‘t ask me why! Supernatural class!!!")
Now you task is to help lzqxh to compute the minimum cost!
Input
The input contains multiple test cases.
The first line of each case consists of two integers, N (N<=50) and M (M<=2000).
The following line contains N integers, representing a[1] to a[N]. The sum of a[1] to a[N] will not exceed 500.
The next M lines, each have five integers, indicating c[i], L1[i], d[i], L2[i] and money[i] (1<=c[i], d[i]<=N, 0<=L1[i]<=a[c[i]], 0<=L2[i]<=a[d[i]], money[i]<=1000) for the i-th tutorial class. The courses are numbered from 1 to N.
The input is terminated by N = M = 0.
The first line of each case consists of two integers, N (N<=50) and M (M<=2000).
The following line contains N integers, representing a[1] to a[N]. The sum of a[1] to a[N] will not exceed 500.
The next M lines, each have five integers, indicating c[i], L1[i], d[i], L2[i] and money[i] (1<=c[i], d[i]<=N, 0<=L1[i]<=a[c[i]], 0<=L2[i]<=a[d[i]], money[i]<=1000) for the i-th tutorial class. The courses are numbered from 1 to N.
The input is terminated by N = M = 0.
Output
Output the minimum cost for achieving lzqxh‘s target in a line. If his target can‘t be achieved, just output -1.
Sample Input
3 4 3 3 1 1 0 2 3 10 2 1 1 2 10 1 2 3 1 10 3 1 1 3 10 0 0
Sample Output
40
题意:给出了n个科目,以及每门科目需要达到的等级,然后给出了m堂课,以及修每堂课要求达到的科目等级,修完以后可以获得的科目等级以及修这门课的花费,然后求每
门科目都到达满级的最小花费,如果不能完成则输出-1
思路:将每门科目的每个等级看成一个点,然后对于同一门科目,等级 i 向等级 i-1 连一条边,花费为0,然后给出的m堂课程,从要求的科目等级 i 向可以获得的科目等级 j 连
边,花费为给出的花费,将所有课程的等级0缩成一个根结点,然后问题就转化为求最小树形图,也叫有向图上的最小生成树,直接套板子搞定~
<script src="https://code.csdn.net/snippets/458552.js" type="text/javascript"></script>
2014多校9(1007)hdu4966(最小树形图)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。