Preparing NOJ

大飞机项目

3000ms 65536K

Description:

大飞机指起飞总重超过100吨的运输类飞机,包括军用大型运输机和民用大型运输机,也包括一次航程达到3000公里的军用或100座位以上的民用客机。国际航运体系习惯上把300座位以上的客机称作“大型客机”,在我国,一般把150座以上客机称为“大型客机”。

随着民用航空快速发展和国防现代化步伐加快,中国对大型飞机的需求日益紧迫。自主研制大型飞机,发展有市场竞争力的航空产业,对于转变经济增长方式、带动科学技术发展、增强国家综合实力和国际竞争力,加快现代化步伐,具有重大意义。中国航空工业经过多年的发展,已经具备发展大型飞机的技术和物质基础。20072月,国务院原则批准大型飞机研制重大科技专项正式立项。


但自主制造大飞机非常复杂,需要在全球范围内配置部件,联合多个公司通力合作才能完成。假设从开始制造到完成一架飞机中间需要完成n个部件,这些部件可能由多个公司协作完成有关部分(称为一道工序),当然每道工序所耗费的时间可能是不同的。现请你根据给定数据,确定哪些工序是关键的,不能提早,也不能拖延。

Input:

第一行是一个正整数:测试用例数目,最多为100。之后,每个测试用例包括多行:

l       1行给出两个整数(空格分隔),第一个整数表示部件数n2n200,第二个整数表示工序数m0m20100

l       m行,每行三个整数(空格分隔),前两个整数表示两个部件;第三个整数表示涉及上述两个部件的工序需要花费的时间t,部件用序号表示,分别为1n,这里假设飞机制造启动用0号序号表示,飞机制造完成用n+1号序号表示;一道工序用前后的部件表示,例如,如果12部件之间存在一道工序,则这道工序表示为(1,2)

Output:

对于每个测试用例:

l       按照制造顺序给出关键工序

注意:(1每个测试用例关键工序之间没有空格;

 (2)输出部分的结尾要求包含一个多余的空行。

 (3)(4,5)和(4,7)均为关键工序时,先输出(4,7),再输出(4,5)

Sample Input:

2
1 2
0 1 1
1 2 2
2 4
0 1 2
1 2 3
2 3 5
0 3 18

Sample Output:

(0,1)(1,2)
(0,3)

Note:

本题由旧版NOJ导入,来源:算法与数据结构设计考核赛2009

Info

NOJ

Provider NOJ

Code NOJ1132

Tags

Submitted 3

Passed 1

AC Rate 33.33%

Date 04/20/2019 10:03:10

Related

Nothing Yet