UVa 804 Petri Net Simulation

题目分析Petri\texttt{Petri}Petri网是一种用于描述并发系统的计算模型由库所Places\texttt{Places}Places、变迁Transitions\texttt{Transitions}Transitions和有向边组成。每个库所可以包含零个或多个令牌Tokens\texttt{Tokens}Tokens。本题要求模拟Petri\texttt{Petri}Petri网的运行过程变迁在所有输入库所都有足够令牌时可以被触发触发时从每个输入库所移除一个令牌向每个输出库所添加一个令牌当多个变迁都可触发时可以选择任意一个触发模拟最多NFNFNF次触发或在无可用变迁时提前结束解题思路关键观察触发条件判断当变迁的某个输入库所在输入列表中出现多次时需要该库所的令牌数 ≥ 出现次数选择策略按变迁编号从小到大检查选择第一个可触发的模拟过程循环执行触发操作直到达到NFNFNF次或无可用变迁算法步骤数据结构使用数组存储库所令牌数结构体数组存储变迁的输入输出信息触发检查对于每个变迁统计各输入库所所需的最小令牌数模拟循环每次选择可触发的变迁更新令牌分布输出结果根据模拟情况输出存活/死亡状态及剩余令牌分布参考代码// Petri Net Simulation// UVa ID: 804// Verdict: Accepted// Submission Date: 2025-11-01// UVa Run Time: 0.240s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structTransition{vectorintinput,output;};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intNP,T1;while(cinNPNP){vectorintplaces(NP1);for(inti1;iNP;i)cinplaces[i];intNT;cinNT;vectorTransitionts(NT1);for(intt1;tNT;t){intx;while(cinxx){if(x0)ts[t].input.push_back(-x);elsets[t].output.push_back(x);}}intNF;cinNF;intfired0,live1;for(;firedNF;fired){intenabled-1;for(intt1;tNT;t){vectorintcnt(NP1,0);for(intp:ts[t].input)cnt[p];boolcanFiredtrue;for(inti1;iNPcanFired;i)if(places[i]cnt[i])canFiredfalse;if(canFired){enabledt;break;}}if(enabled-1){live0;break;}for(intp:ts[enabled].input)places[p]--;for(intp:ts[enabled].output)places[p];}coutCase T: ;if(live)coutstill live after NF transitions\n;elsecoutdead after fired transitions\n;coutPlaces with tokens:;for(inti1;iNP;i)if(places[i]0)cout i (places[i]);cout\n\n;T;}return0;}