每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

题目描述

你的任务是模拟Petri网的变迁。Petri网包含NP个库所（用P1，P2…表示）和NT个变迁（用T1，T2…表示）。0<NP, NT<100。当每个变迁的每个输入库所都至少有一个token时，变迁是允许的。变迁发生的结果是每个输入库所减少一个token，每个输出库所增加一个 token。变迁的发生是原子性的，即所有token的增加和减少应同时进行。注意，一个变迁可能有多个相同的输入或者输出。如果一个库所在变迁的输入库所列表中出现了两次，则token 会减少两个。输出库所也是类似。如果有多个变迁是允许的，一次只能发生一个。
如图6-24所示，一开始只有T1是允许的，发生一次T1变迁之后有一个token会从P1移动
到P2，但仍然只有T1是允许的，因为T2要求P2有两个token。再发生一次T1变迁之后P1中只剩一个token，而P2中有两个，因为T1和T2都可以发生。假定T2发生，则P2中不再有token，
而P3中有一个token，因此T1和T3都是允许的。

HINT

输入一个Petri网络。初始时每个库所都有一个token。每个变迁用一个整数序列表示，负数表示输入库所，正数表示输出库所。每个变迁至少包含一个输入和一个输出。最后输入一个整数NF，表示要发生NF次变迁（同时有多个变迁允许时可以任选一个发生，输入保证这
个选择不会影响最终结果）。

依次对每个T(i)进行执行，如果每个input都能执行成功（NP中有token）则执行，则执行output，并将执行T(i)的次数++，否则恢复刚才所有执行的input。一轮（将所有T(i)执行一遍）中任意一个T(i)执行就可以执行下一轮。如果一轮中没有任何一个T(i)执行成功则说明执行失败，返回执行次数。

代码

#include<iostream>
#include<cstring>
#include<string>

using namespace std;

int deal();

const int MAXN = 100 + 10;

int NP[MAXN];           //P(i)现存小球的数量
int NT_in[MAXN][MAXN];      //存储T(i)的input
int NT_out[MAXN][MAXN];     //存储T(i)的output
int n, m, num;

int main()
{
    int kase = 0;
    while (cin >> n && n)
    {
        //初始化
        memset(NT_in,0,sizeof(NT_in));
        memset(NT_out, 0, sizeof(NT_out));
        int k,i, j, x, do_num;
        for (i = 1; i <= n; i++) cin >> NP[i];
        cin >> m;
        for (i = 0; i < m; i++){
            k = j = 0;
            while (cin >> x && x){
                if (x < 0) NT_in[i][j++] = x;
                else NT_out[i][k++] = x;
            }
        }
        cin >> num;
        //处理
        do_num = deal(); //处理函数，返回执行变迁的次数
        //输出
        if(do_num == num) cout << "Case " << ++kase << ": still live after " << do_num << " transitions\n";
        else cout << "Case " << ++kase << ": dead after " << do_num << " transitions\n";
        cout << "Places with tokens:";
        for (int i = 1; i <= n; i++)        //逐个输出有token的P,和个数
            if (NP[i] > 0)  cout << " " << i << " (" << NP[i] << ")";
        cout << endl << endl;
    }
    return 0;
}
/*依次对每个T(i)进行执行，如果每个input都能执行成功（NP中有token）则执行，
则执行output，并将执行T(i)的次数++，否则恢复刚才所有执行的input。
一轮（将所有T(i)执行一遍）中任意一个T(i)执行就可以执行下一轮。
如果一轮中没有任何一个T(i)执行成功则说明执行失败，返回执行次数。*/
int deal()
{
    int i, j, n = 1;
    while(1)
    {
        bool had_do = false; //该轮中有T(i)执行，可以执行下一轮
        for (i = 0; i < m; i++){
            j = 0; bool can_do = true;//该T(i)执行是否成功
            while (NT_in[i][j] != 0){
                if (NP[-NT_in[i][j]] > 0)   //执行input
                    NP[-NT_in[i][j++]]--;
                else{                    //input执行失败，恢复input之前状态，并将can_do置为false

                    while (j--)
                        NP[-NT_in[i][j]]++;
                    can_do = false; break;
                }
            }
            if (can_do) {               //input执行成功的情况下执行output
                j = 0; n++;//***
                while (NT_out[i][j] != 0){
                    NP[NT_out[i][j]]++;
                    j++;
                }
                had_do = true;
                if (n > num) return num;
            }
            else break;
        }
        if (!had_do) return n-1;
    }
}

总结

重点在于理解题意