475. 工程規劃

工程规划

程序名称：projecta

输入文件：projecta.in

输出文件：projecta.out

问题描述：

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

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

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

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

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

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

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

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

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

输入

    输入文件的第一行为项目总数N（1≤N≤100)，设项目的编号依次为1，2，…，N。下面N行依次为完成每个项目所需的工作时间（每个项目占一行）。这个时间为不超过100的正整数。

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

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

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

    整个文件以一个字母“＃”表示结束（单独占一行）

输出

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

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

输入输出示例

projecta.in

3

2

3

4

SAF 2 1

FAF 3 2

＃

projecta.out

1 0

2 2

3 1

projecta.in

3

1

1

1

SAF 2 1

SAF 3 2

SAF 1 3

＃

projecta.out

0