Dotcpp  >  编程题库  >  蓝桥杯算法提高VIP-Petri Net Simulation
题目 1890:

蓝桥杯算法提高VIP-Petri Net Simulation

时间限制: 2s 内存限制: 192MB 提交: 7 解决: 3

题目描述

一个Petri网是一个计算模型,用来说明并发事件。每个Petri网包含一些库所(被表示成圆圈),变迁(被表示成黑色的矩形),和一些有向边,用来连接库所到变迁,和变迁到库所。每个库所能够包含0个或多个令牌(被表示成黑点)。
这里有2个例子:

 蓝桥杯算法提高VIP-Petri Net Simulation

 蓝桥杯算法提高VIP-Petri Net Simulation
在上面的第一个Petri网中,有2个库所(P1 和 P2)和2个变迁(T1 和 T2)。P1初始有1个令牌。P2没有令牌。P1是变迁T1的输入库所,P2是T1的输出库所。在第二个例子中,有3个库所和3个变迁,P1有3个令牌。T2有2个输入库所,2个都是P2。

一个Petri网的操作

每个Petri网的变迁要么被允许,要么不被允许。一个变迁被允许当且仅当每个输入库所都至少有1个令牌。任何被允许的变迁可以发生。如果有多个变迁被允许,任何一个都可能发生。当一个变迁发生时,每个输入库所都会移除1个令牌,每个输出库所都会增加1个令牌。这会有效地利用原子能来完成,作为一个事件。如果没有一个变迁被允许,这个Petri网就被认为是死的。

最上面那个例子,只有T1是被允许的。当它发生时,会从P1移除1个令牌,给P2增加1个令牌。然后T2就被允许了。当它发生时,会从P2移除1个令牌,给P1增加1个令牌。显然,这个Petri网将会永远重复这个循环。

下面那个例子更加有趣。T1被允许然后发生,有效地移动1个令牌给P2。在这个时候,T1仍然是唯一被允许的变迁(T2被允许需要P2有2个令牌)。T1再次发生,在P1剩下1个令牌,P2中有2个令牌。现在,T1和T2都被允许。假设T2发生,从P2移除2个令牌,给P3增加1个令牌。现在T1和T3都被允许。直到没有变迁被允许,你应该能看到在9次变迁发生后,在P2仅留下1个令牌。(注意到,如果当T1和T2都被允许的时候,T1代替了T2发生,这个结果也同样是在9次变迁发生后。)

在这个问题中,你将会被给出1个或多个Petri网的描述。对于每个描述,你将要模拟NF(0 < NF < 1000)次变迁的发生,然后输出留在库所里的令牌数量。如果这个Petri网在NF次变迁发生之前就死了,你将按事实输出。

输入格式

每个Petri网的描述首先会包含一个整数NP(0 < NP < 100),紧接着有NP个整数分别表示编号为1,2,…,NP的库所初始有多个个令牌。接着会有一个整数NT(0 < NT < 100)表示变迁的数量。然后,对于每个变迁(编号为1,2,…,NT)将会有一个以0结尾的整数序列。序列中的负数代表输入库所,所以数字-n代表有一个输入库所在n。序列中的正数代表输出库所,所以数字p代表有一个输出库所在p。每个库所至少有一个输入库所,至少有一个输出库所。最后,在NT个变迁的描述之后,会有一个整数代表你至多要模拟变迁发生的次数,NF。输入会包含一个或多个Petri网的描述,最后会有一个0。

输出格式

对于每个Petri网的描述,输出三行。第一行输出是第几组数据(从1开始连续编号)和是否有NF次变迁发生。如果有,输出这个Petri网在NF次变迁发生后仍然活着。否则输出这个Petri网已经死了和变迁发生的次数。两种情况下,在第二行都输出在模拟结束后,包含1个或多个令牌的库所的编号,和每个这种库所含有的令牌数量。输出的序列按编号递增。每组数据的第三行都应该是空行。
输入数据将会被选择来保证正确输出的唯一性。

样例输入

2
1 0
2
-1 2 0
-2 1 0
100
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
100
0

样例输出

Case 1: still live after 100 transitions
Places with tokens: 1 (1)

Case 2: dead after 9 transitions
Places with tokens: 2 (1)

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签