题目 1890:
蓝桥杯算法提高VIP-Petri Net Simulation
时间限制: 2s
内存限制: 192MB 提交: 7 解决: 3
题目描述
一个Petri网是一个计算模型，用来说明并发事件。每个Petri网包含一些库所（被表示成圆圈），变迁（被表示成黑色的矩形），和一些有向边，用来连接库所到变迁，和变迁到库所。每个库所能够包含0个或多个令牌（被表示成黑点）。
这里有2个例子：
在上面的第一个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次变迁发生之前就死了，你将按事实输出。
这里有2个例子：
在上面的第一个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)