首页 > 试题广场 >

工厂流水线

[编程题]工厂流水线
  • 热度指数:7 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
现代化工厂的生产,讲究流水化作业,只有合理的作业安排,才能保证较高的生产效率。工作人员给出了他们手动安排的机器流水线作业表,但碍于机器数量以及工序较多,人为检验方案是否可行,难度较大,你能否通过编写程序来帮助他们检验呢?
工厂流水线作业机制如下:
工厂生产的产品是由一步步零件不断加工和装配完成的。产品的加工需按照严格的工序进行,即只有一个零件所需的全部组件的上一步工序完成,才能进行下一步工序,且保证上一步的组件只会被下一步中一个零件引用,每台机器同时开始加工,流水线严格按照时序进行,不存在等待情况。
示意图中的黑线代表工序先后关系,样例1情况如下:

样例2情况如下所示,黑×位置的工序关系不成立,故方案不可行。


输入描述:
第一行输入一个正整数t(t<=200),代表检验的方案数。随后每组数据第一行,输入一个正整数n(n<=30),代表机器数量。随后n组数据,每组数据第一行输入一个正整数m(m<=30),代表该机器上的加工零件数。随后m组数据,每组数据第一行三个正整数,id(零件在该方案中唯一的id号),time(该项零件加工完成所需的小时数),p(该零件加工需要几个零件),随后p行,每行一个正整数idx,分别代表该零件加工所需的零件id。


输出描述:
对于每个方案,若该方案中每组零件都能严格按照流水线机制完成生产,则输出“Yes”,否则输出“No”。
示例1

输入

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

输出

Yes
No

这道题你会答吗?花几分钟告诉大家答案吧!