XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 6-7UVa804 - Petri Net Simulation

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题意：模拟Petri网的执行。虽然没听说过Petri网，但是题目描述的很清晰。

代码：（Accepted，0.210s）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//UVa804 - Petri Net Simulation
//Accepted 0.210s
//#define _XIENAOBAN_
#include<iostream>
#include<map>
using namespace std;

struct {
	map<int, int> ipt, opt;
} Trans[111];

int NP, NT, NF, Cnt, T(0);
int Token[111];

void IniAndInput() {
	Cnt = 0;
	for (int i(1);i <= NP;++i)
		scanf("%d", Token + i);
	scanf("%d", &NT);
	for (int i(1);i <= NT;++i) {
		Trans[i].ipt.clear();
		Trans[i].opt.clear();
		int n;
		while (scanf("%d", &n) != EOF && n) {
			if (n < 0) ++Trans[i].ipt[-n];
			else ++Trans[i].opt[n];
		}
	}
	scanf("%d", &NF);
}

bool JudgeTrans(int i) {
	for (auto& t : Trans[i].ipt)
		if (Token[t.first] < t.second)
			return false;
	return true;
}

bool TryTrans() {
	for (int i(1);i <= NT;++i) {
		if (!JudgeTrans(i)) continue;
		for (auto& t : Trans[i].ipt)
			Token[t.first] -= t.second;
		for (auto& t : Trans[i].opt)
			Token[t.first] += t.second;
		return true;
	}
	return false;
}

void Output() {
	printf("Case %d: ", ++T);
	if (Cnt < NF)
		printf("dead after %d transitions\n", Cnt);
	else printf("still live after %d transitions\n", NF);
	printf("Places with tokens:");
	for (int i(1);i <= NP;++i) if (Token[i])
		printf(" %d (%d)", i, Token[i]);
	printf("\n\n");
}

void Debug() {
	cerr << "\nToken:\n";
	for (int i(1);i <= NP;++i) cerr << Token[i] << ' ';
	cerr << "\nTrans:\n";
	for (int i(1);i <= NT;++i) {
		for (const auto& t : Trans[i].ipt) cerr << t.first << " - " << t.second << '\n';
		for (const auto& t : Trans[i].opt) cerr << t.first << " + " << t.second << '\n';
	}
}

int main()
{
#ifdef _XIENAOBAN_
#define gets(T) gets_s(T, 129)
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	while (scanf("%d", &NP) != EOF && NP) {
		IniAndInput();
		//Debug();//
		for (;Cnt < NF;++Cnt) {
			if (!TryTrans()) break;
			//Debug();//
		}
		Output();
	}
	return 0;
}

分析：其实就是无脑模拟。比前一题简单好多，有些意外。一遍通过，好久没一遍过了，好爽。题目描述的很清晰，看紫书的中文简述反而看不懂。这次尽量给不同部分分了个块，分到不同函数里去了，看着清晰点。210ms好像有点长，看网上别人的做法也基本类似，也不优化了。 说起来我一开始对每一个Case进行初始化Trans数组时，一开始选择的对整个数组的ipt、opt进行clear，用时190ms。后来改成只对要用的部分进行clear初始化，反而用时更长了（210ms）。这应该是处理器的优化的结果吧。就是让处理器反复干一件事时它会预测下一步还是这个同样的计算，就会处理的特别快。也算是硬件因素吧？