1646: 工程计划
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
― 工程小组将一个工程分为若干个项目，每个项目都可以独立进行。所有项目都工作完毕时，整个工程也就完成了。每个项目都需要一定的工作时间。工程最后总耗时是从第一个项目开始到最后一个项目结束的这段时间。
― 各个项目之间可能存在制约关系：
◦ SAS p q (p Sart After q Start，p在q开始之后才能开始）
◦ FAS p q (p Finish After q Start，p在q开始之后才能结束）
◦ SAF p q (p Sart After q Finish，p在q结束之后才能开始）
◦ FAF p q (p Finish After q Finish，p在q结束之后才能结束）
― 如果没有制约关系，则可同时进行。
― 请你根据各个项目的工作时间及先后关系，找出一种安排工程的方案，使整个工程尽可能快的完成。
输入
― 输入文件的第一行为项目总数N（1≤N≤100)，设项目的编号依次为1，2，…，N。下面N行依次为完成每个项目所需的工作时间（每个项目占一行）。这个时间为不超过100的正整数。
― 接下来若干行是一些项目间先后次序关系的列表，每行的格式为：<先后次序关系符> <项目p编号> <项目q编号>
以#结束
输出
― 若问题有解，则输出文件有N行，依次输出项目1到项目N的最早开始时间（设整个工程从0时刻开始）。
― 若问题无解，则输出0。
样例输入 复制
10
2
7
5
3
4
6
2
1
1
3
SAS 9 8
SAS 10 5
SAF 1 2
FAF 3 2
SAF 4 3
SAS 4 5
FAF 5 3
FAS 6 5
FAF 7 6
FAF 10 6
SAF 7 8
FAF 9 7
FAF 10 9
#样例输出 复制
1 7
2 0
3 2
4 7
5 3
6 0
7 4
8 0
9 5
10 3