工程计划

Grade 100 Open Time Wednesday, 17 June 2020, 9:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:25 PM
Input file project.in Output file project.out

【题目描述】工程计划(project)HDU 4109

一个大工程由无数的子计划组成,这些子计划之间存在一种先后关系,即某些子计划必须在其他一些计划完成一段时间之后才能开始。除此之外,各子计划可以同步进行且各子计划完成的时间为1个月。现在给出各子计划之间的关系图,请分析完成所有的计划需要多少时间?

【输入格式】

输入包含多组测试数据。

第一行包含两个整数N,M (N≤1 000,M≤10 000),表示有N个项目和M个依存关系。

随后M行,每行包含三个整数X,Y,Z,表示必须完成X子计划才能执行Y子计划,且花费时间为Z。各子计划的标号为0 ~N-1。

【输出格式】

输出完成所有计划需要的时间。

【输入样例】

5 2

1 2 1

3 4 1

【输出样例】

2

【样例说明】

第1个月,子计划0、1 和 3被完成;

第2个月,子计划2 和4被完成;

所以最短完成时间为2个月。