低碳工程

　　2010年是河北省三年大变样的决胜年，保定作为联合国世界和谐城市试验区、低碳城市，市政府决定进行一项低碳工程，用来进一步减少碳的排放量。该项工程分为N(3≤N≤10000)个作业步骤，分别用标号1,2,...,N表示。每个作业分别需要用T_i个时间单位(1≤T_i≤1000,i=1,2,...,N)。根据工程师的要求，作业需按照一定次序完成，每个作业可以有M_i(0≤M_i≤100)个前提作业。一个作业当且仅当没有前提作业或前提作业均完成时才可进行。工程建设公司拥有充足的工力，可以保证多个作业并行进行。
　　现在请你编程序计算一下，完成整个低碳工程至少需要多少个时间单位。若作业的前提关系出现矛盾，即工程永远不可能完成，请输出"No Solution"，以便工程师修改工程计划。
　　例如：某工程由1,2,3,4四个作业组成，分别需要3,5,4,5个时间单位，作业2和作业3的前提作业均只有一个，为作业1，作业4有两个前提作业——作业2和作业3。则工程队可按如下策略进行施工：先用3个时间单位完成作业1，之后作业2和作业3并行进行，5个时间单位后两个工程均完成，在进行作业4，花费5个时间单位，则整个工程共需13个时间单位。可以证明，该方案是竣工最早的方案之一。又例如：工程有两个作业，作业1以作业2为前提条件，作业2以作业1为前提条件，则该工程无法完成。

　　输入数据包含若干组测试样例；
　　第一行为一个整数C，表示共C组测试数据；
　　每组测试数据的格式如下：
　　第一行为一个整数N(3≤N≤10000)，表示有N个作业；
　　接下来的N行数据，依次描述编号为1,2,...,N的作业：
　　每行的第一个整数为T_i，表示完成该作业所需时间；
　　第二个整数M(0≤M_i≤100)表示该作业的前提作业的数量；
　　接下来是M个整数，P₁,P₂,...,P_M，表示每个前提作业的编号；
　　同一行的各个数据之间以一个空格隔开。

　　对于每组测试数据，对应的输出只有一行：
　　若作业的前提条件没有矛盾，请输出一个整数，表示完成整个低碳工程所需时间；
　　否则，输出一行字符串"No Solution."。（双引号本身不输出，注意末尾的句号）

3
4
3 0
5 1 1
4 1 1
5 2 2 3
3
5 1 3
5 1 1
5 1 2
7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

13
No Solution.
23

河北大学算法艺术协会

2010年河北大学程序设计竞赛

Close | Top

Administration