UVA-804 模拟

将每个translation的输入和输出place全部记录下来，模拟即可，当所有translation都不能工作时，就说明dead了。

AC代码：

#include<cstdio>
#include<vector>
using namespace std;

const int maxn = 100 + 5;

struct node{
    vector<int> in, out;
}tran[maxn];

int p[maxn]; //the number of tokens in  all places

int main(){
    int pn, tn, nf, kase = 1;
    while(scanf("%d", &pn) == 1 && pn){
        for(int i = 1; i <= pn; ++i){
            scanf("%d", &p[i]);
        }
        scanf("%d", &tn);
        for(int i = 1; i <= tn; ++i){
            int x;
            while(scanf("%d", &x) == 1 && x){
                if(x < 0) tran[i].in.push_back(-x);
                else tran[i].out.push_back(x);
            }
        }
        scanf("%d",&nf);
        bool dead = 0;
        int h;
        for(h = 0; h < nf; ++h){
            int cnt = 0;
            for(int i = 1; i <= tn; ++i){
                bool flag = 1;
                vector<int> &in = tran[i].in, &out = tran[i].out;
                for(int j = 0; j < in.size(); ++j){
                    if(p[in[j]] == 0) {
                        flag = 0;
                        while(j) p[in[--j]]++; //
                        break;
                    }
                    else p[in[j]]--;
                }
                if(!flag) ++cnt;
                else {
                    for(int k = 0; k < out.size(); ++k) p[out[k]]++;
                    break;
                }
            }
            if(cnt == tn) {
               dead = 1;
               break;
            }
        }
        if(dead) printf("Case %d: dead after %d transitions\n", kase++, h);
        else printf("Case %d: still live after %d transitions\n", kase++, nf);
        printf("Places with tokens:");
        for(int i = 1; i <= pn ; ++i){
            if(p[i]) printf(" %d (%d)", i, p[i]);
        }
        printf("\n\n");
        for(int i = 1; i <= tn ; ++i) {
            tran[i].in.clear();
            tran[i].out.clear();
        }
    }
    return 0;
}

如有不当之处欢迎指出！

巴特西

UVA-804 模拟

最新文章

热门文章