工程计划

题目描述:

      工程组是一讲究效率的工程小组。为了规划和管理的方便，他们将一个工作分为若干个项目，每个项目都可以独立进行。所有项目都工作完毕时，整个工程也就完成了。每个项目需要一定的工作时间。工程最后总耗时是从第一个项目开始到最后一个项目结束的这段时间。

    各个项目之间可以存在也可以不存在相互制约关系。如果有制约关系，则可能是以下四种之一（设两个项目分别为p和q）：

（1）SAS p q ( p Start After q Start，项目p在项目q开始之后才能开始）。

（2）FAS p q ( p Finish After q Start，项目p在项目q开始之后才能结束）。

（3）SAF p q ( p Start After q Finish，项目p在项目q结束之后才能开始）。

（4）FAF p q ( p Finish After q Finish，项目p在项目q结束之后才能结束）。

     如果没有制约关系，则可同时进行。

     例如：SAF 1 3 表示项目1必须在项目3完成后才能开始。若项目3工作时间为3，起始时刻为2，则项目1最早在时刻5才能开始。

      作为项目的负责人，请你根据各个项目的工作时间及先后关系，找出一种安排工程的方案，使整个工作尽可能快地完成。

输入格式:

多组测试数据，每组测试数据包括：

第一行为项目总数N ( 1<= N <=200 ）， 设项目的编号依次为1， 2， ... ， N。下面N行依次为完成每个项目所需的工作时间（每个项目占一行）。这个时间为不超过100的正整数。

接下来若干行是一些项目间先后次序关系的列表，每行的格式为：

<先后次序关系符>（<项目p编程> ( <项目q编号>

其中：<先后次序关系符>为SAS、FAS、SAF、FAF中的任意一个，“（”表示一个空格符。

输入以一个字母“#”表示结束（单独占一行）。

输出格式:

每组测试数据，输出内容如下：

若问题有解，则输出N行，依次输出项目1到项目N的最早开始时间（设整个工作从0时刻开始）。 每行的格式为：

项目编号 最早开始时间。

若问题无解，则输出只有一行，为一个整数0。

样例输入:

3
2
3
4
SAF 2 1
FAF 3 2
#
3
1
1
1
SAF 2 1
SAF 3 2
SAF 1 3
#

样例输出:

Case 1:
1 0
2 2
3 1

Case 2:
0

时间限制: 1000ms
空间限制: 256MB

---