Problem UVA804-Petri Net Simulation
Accept：251 Submit：1975
Time Limit: 3000 mSec
Problem Description
Input
Each Petri net description will first contain an integer NP (0 < NP < 100) followed by NP integers specifying the number of tokens initially in each of the places numbered 1,2,...,NP. Next there will appear an integer NT (0 < NT < 100) specifying the number of transitions. Then, for each transition (in increasing numerical order 1,2,...,NT) there will appear a list of integers terminated by zero. The negative numbers in the list will represent the input places, so the number −n indicates there is an input place at n. The positive numbers in the list will indicate the output places, so the number p indicates an output place at p. There will be at least one input place and at least one output place for each transition. Finally, after the description of all NT transitions, there will appear an integer indicating the maximum number of firings you are to simulate, NF. The input will contain one or more Petri net descriptions followed by a zero.
Output
For each Petri net description in the input display three lines of output. On the first line indicate the number of the input case (numbered sequentially starting with 1) and whether or not NF transitions were able to fire. If so, indicate the net is still live after NF firings. Otherwise indicate the net is dead, and the number of firings which were completed. In either case, on the second line give the identities of the places which contain one or more tokens after the simulation, and the number of tokens each such place contains. This list should be in ascending order. The third line of output for each set should be blank. The input data will be selected to guarantee the uniqueness of the correct output displays.
Sample Input
Sample Ouput
Case 1: still live after 100 transitions
Places with tokens: 1 (1)
Case 2: dead after 9 transitions
Places with tokens: 2 (1)
题解：这个题就是个模拟，题意稍有一些难懂（英文比紫书的中文好懂......）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 using namespace std; 7 8 const int maxn = 100+5; 9 10 struct Place{ 11 int token; 12 }place[maxn]; 13 14 struct Point{ 15 int pos,sum; 16 Point(int pos = 0,int sum = 0) : 17 pos(pos),sum(sum) {} 18 }; 19 20 struct Tra{ 21 vector<Point> input,output; 22 }Tra[maxn]; 23 24 int n,m,iCase = 1; 25 int in[maxn],out[maxn]; 26 27 bool solve(){ 28 for(int i = 1;i <= m;i++){ 29 bool ok = true; 30 for(int j = 0;j < (int)Tra[i].input.size();j++){ 31 int pos = Tra[i].input[j].pos; 32 int sum = Tra[i].input[j].sum; 33 if(place[pos].token < sum){ 34 ok = false; 35 break; 36 } 37 } 38 if(ok){ 39 for(int k = 0;k < (int)Tra[i].input.size();k++){ 40 int pos = Tra[i].input[k].pos; 41 int sum = Tra[i].input[k].sum; 42 place[pos].token -= sum; 43 } 44 for(int k = 0;k < (int)Tra[i].output.size();k++){ 45 int pos = Tra[i].output[k].pos; 46 int sum = Tra[i].output[k].sum; 47 place[pos].token += sum; 48 } 49 return true; 50 } 51 } 52 return false; 53 } 54 55 int main() 56 { 57 //freopen("input.txt","r",stdin); 58 while(~scanf("%d",&n) && n){ 59 for(int i = 1;i <= n;i++){ 60 scanf("%d",&place[i].token); 61 } 62 scanf("%d",&m); 63 for(int i = 1;i <= m;i++){ 64 Tra[i].input.clear(); 65 Tra[i].output.clear(); 66 } 67 int x; 68 for(int i = 1;i <= m;i++){ 69 memset(in,0,sizeof(in)); 70 memset(out,0,sizeof(out)); 71 while(scanf("%d",&x) && x){ 72 if(x < 0) in[-x]++; 73 else out[x]++; 74 } 75 for(int t = 1;t <= n;t++){ 76 if(in[t]) Tra[i].input.push_back(Point(t,in[t])); 77 if(out[t]) Tra[i].output.push_back(Point(t,out[t])); 78 } 79 } 80 int round; 81 scanf("%d",&round); 82 int tt; 83 for(tt = 1;tt <= round;tt++){ 84 if(!solve()) break; 85 } 86 printf("Case %d: ",iCase++); 87 if(tt > round) printf("still live after %d transitions ",round); 88 else printf("dead after %d transitions ",tt-1); 89 printf("Places with tokens:"); 90 for(int i = 1;i <= n;i++){ 91 if(place[i].token){ 92 printf(" %d (%d)",i,place[i].token); 93 } 94 } 95 printf(" "); 96 } 97 return 0; 98 }