题目分析
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//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structTransition{vector<int>input,output;};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intNP,T=1;while(cin>>NP&&NP){vector<int>places(NP+1);for(inti=1;i<=NP;i++)cin>>places[i];intNT;cin>>NT;vector<Transition>ts(NT+1);for(intt=1;t<=NT;t++){intx;while(cin>>x&&x){if(x<0)ts[t].input.push_back(-x);elsets[t].output.push_back(x);}}intNF;cin>>NF;intfired=0,live=1;for(;fired<NF;fired++){intenabled=-1;for(intt=1;t<=NT;t++){vector<int>cnt(NP+1,0);for(intp:ts[t].input)cnt[p]++;boolcanFired=true;for(inti=1;i<=NP&&canFired;i++)if(places[i]<cnt[i])canFired=false;if(canFired){enabled=t;break;}}if(enabled==-1){live=0;break;}for(intp:ts[enabled].input)places[p]--;for(intp:ts[enabled].output)places[p]++;}cout<<"Case "<<T<<": ";if(live)cout<<"still live after "<<NF<<" transitions\n";elsecout<<"dead after "<<fired<<" transitions\n";cout<<"Places with tokens:";for(inti=1;i<=NP;i++)if(places[i]>0)cout<<" "<<i<<" ("<<places[i]<<")";cout<<"\n\n";T++;}return0;}
