工程规划关键路径 数据结构
工程规划(project)
问题描述：

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。
输入输出示例1：
project .in
3
2
3
4
SAF 2 1
FAF 3 2
＃

project .out
1 0
2 2
3 1
输入输出示例2：
project .in
3
1
1
1
SAF 2 1
SAF 3 2
SAF 1 3
＃

project .out
0

思路：用求关键路径算法实现。

[解决办法]
我来发一个，抛砖引玉
下面程序使用VS2005+Vista测试通过

#include <vector>
#include <list>
#include <iostream>
#include <string>

enum ProjectStatus
{
PRE_START, //没有开始
STARTED, //已经开始，但是还没有完成
FINISHED //完成
};

class RuleIf
{
public:
virtual ~RuleIf(){}
virtual bool canStart() = 0;
virtual bool canFinish() = 0;
virtual void correct() = 0; //修正工程的开始结束时间
};

struct ProjectInfo
{
int iStartTime;
int iFinishTime;
ProjectStatus eState;
unsigned int uiTimeLimit;
ProjectInfo(unsigned int _uiTimeLimit = 0) : iStartTime(0),
iFinishTime(_uiTimeLimit),
eState(PRE_START),
uiTimeLimit(_uiTimeLimit)
{}

std::list<RuleIf*> rules;
};

class SASRule : public RuleIf
{
public:
virtual bool canStart(){
return m_proDepended.eState != PRE_START;
}
virtual bool canFinish(){
return canStart(); //不限制能否结束
}
virtual void correct() //修正工程的开始结束时间
{
m_curr.iStartTime = std::max(m_curr.iStartTime, m_proDepended.iStartTime);
m_curr.iFinishTime = std::max(m_curr.iFinishTime, m_curr.iStartTime + int(m_curr.uiTimeLimit));
}
SASRule(ProjectInfo& curr, const ProjectInfo& proDepended) : m_curr(curr),
m_proDepended(proDepended){}
private:
ProjectInfo& m_curr;
const ProjectInfo& m_proDepended;
};

class SAFRule : public RuleIf
{
public:
virtual bool canStart(){
return m_proDepended.eState == FINISHED;
}
virtual bool canFinish(){
return canStart(); //不限制能否结束
}
virtual void correct() //修正工程的开始结束时间
{
m_curr.iStartTime = std::max(m_curr.iStartTime, m_proDepended.iFinishTime);
m_curr.iFinishTime = std::max(m_curr.iFinishTime, m_curr.iStartTime + int(m_curr.uiTimeLimit));
}
SAFRule(ProjectInfo& curr, const ProjectInfo& proDepended) : m_curr(curr),
m_proDepended(proDepended){}
private:
ProjectInfo& m_curr;
const ProjectInfo& m_proDepended;
};

class FASRule : public RuleIf
{
public:
virtual bool canStart(){

return true;
}
virtual bool canFinish(){
return m_proDepended.eState != PRE_START;
}
virtual void correct() //修正工程的开始结束时间
{
m_curr.iFinishTime = std::max(m_curr.iFinishTime, m_proDepended.iStartTime + int(m_curr.uiTimeLimit));
}
FASRule(ProjectInfo& curr, const ProjectInfo& proDepended) : m_curr(curr),
m_proDepended(proDepended){}
private:
ProjectInfo& m_curr;
const ProjectInfo& m_proDepended;
};

class FAFRule : public RuleIf
{
public:
virtual bool canStart(){
return true;
}
virtual bool canFinish(){
return m_proDepended.eState == FINISHED;
}
virtual void correct() //修正工程的开始结束时间
{
m_curr.iFinishTime = std::max(m_curr.iFinishTime, m_proDepended.iFinishTime);
}
FAFRule(ProjectInfo& curr, const ProjectInfo& proDepended) : m_curr(curr),
m_proDepended(proDepended){}
private:
ProjectInfo& m_curr;
const ProjectInfo& m_proDepended;
};

int main(int, char**)
{
std::vector<ProjectInfo*> projects;

//输入所有工程工期
int projectNumber;
std::cin >> projectNumber;
for (int i = 0; i < projectNumber; ++i)
{
unsigned int uiTimeLimit;
std::cin >> uiTimeLimit;
projects.push_back(new ProjectInfo(uiTimeLimit));
}

//输入工程间的依赖关系
std::string ruleTy;
while (std::cin >> ruleTy)
{
if (ruleTy == "#") break;
int curr;
int depended;
std::cin >> curr;
--curr;
std::cin >> depended;
--depended;
RuleIf* pRule = NULL;
if (ruleTy == "SAS")
{
pRule = new SASRule(*projects[curr], *projects[depended]);
}
else if (ruleTy == "SAF")
{
pRule = new SAFRule(*projects[curr], *projects[depended]);
}
else if (ruleTy == "FAS")
{
pRule = new FASRule(*projects[curr], *projects[depended]);
}
else if (ruleTy == "FAF")
{
pRule = new FAFRule(*projects[curr], *projects[depended]);
}
else break;
projects[curr]->rules.push_back(pRule);
}

bool allFinished = true; //所有工程已完成
bool isDeadLock = true; //是否存在循环依赖，导致工程无法继续

do
{
allFinished = true;
isDeadLock = true;
for (unsigned int i = 0; i < projects.size(); ++i)
{
if (projects[i]->eState == FINISHED) continue;
allFinished = false;
bool canStart = true;
bool canFinish = true;
std::list<RuleIf*>::iterator it = projects[i]->rules.begin();
for (; it != projects[i]->rules.end(); )
{
if (!(*it)->canStart())
{
canStart = false;
++it;
continue;
}
if (!(*it)->canFinish())
{
canFinish = false;
++it;
continue;
}
(*it)->correct();
delete *it;
it = projects[i]->rules.erase(it);
}
if (canStart && (projects[i]->eState == PRE_START)){ //所有约束开工的条件都满足
projects[i]->eState = STARTED;
isDeadLock = false;
}
if (canStart && canFinish && (projects[i]->eState != FINISHED)){ //所有约束完工的条件都满足

projects[i]->eState = FINISHED;
isDeadLock = false;
}
}
}
while (allFinished || isDeadLock);

if (allFinished)
{
for (unsigned int i = 0; i < projects.size(); ++i)
{
//修正工程开始时间
std::cout << projects[i]->iFinishTime - projects[i]->uiTimeLimit << std::endl;
}
}
else
{
std::cout << 0;
}

for (unsigned int i = 0; i < projects.size(); ++i)
{
delete projects[i];
}
projects.clear();

return 0;
}