工程规划（project）

在Microsoft Visual C++ 上运行没有错误; 包括论文word文档、论文答辩的ppt、流程图.vsd等； 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的正整数。 接下来若干行是一些项目间先后次序关系的列表，每行的格式为： 其中：为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 思路：用求关键路径算法实现。

#include 
#include 
#define MAX_VERTEX_NUM 30 //图的最大顶点数
#define MAX 30            //栈的最大容量
#define INFINITY 30000;   //定义最大的最迟发生时间

typedef struct ArcNode
{int adjvex;              //该弧所指向的顶点的位置
 int weight;              //该弧所代表的活动的持续时间
 struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;       //弧结点

typedef struct
{int indegree[MAX_VERTEX_NUM]; //存放各顶点的入度
 ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针
 int vexnumarcnum;                //图的当前顶点和弧数
}Graph;

typedef struct    //定义堆栈结构
{int elem[MAX];   //栈区
 int top;         //栈顶指针
}Stack;

int ve[MAX_VERTEX_NUM];  //全局变量，存放各顶点的最早发生时间
void CreateGraph（Graph *G）;    //生成图的邻接表
int CriticalPath（Graph *G）;    //求图的关键路径
int TopologicalSort（Graph *GStack *T）;  //进行拓扑排序
void FindInDegree（Graph *G）;    //求图各顶点的入度
void Initial（Stack *T）;     //初始化一个堆栈
int Push（Stack *tint a）;  //将一个元素入栈
int Pop（Stack *tint *a）;  //将一个元素出栈
int Gettop（Stack *tint *a）; //得到栈顶元素
int StackEmpty（Stack *S）;  //判断堆栈是否为空

void main（）
{Graph G;  //采用邻接表结构的图
 char j=‘y‘;
 int t;
 printf（“\t\t\t\t本程序为工程规划问题.\n“）;
 printf（“首先输入工程的项目数（顶点数）和事件数（弧数）.\n格式为：项目数，事件数；\n“）;
 printf（“例如：43\n\n“）;
 printf（“接着请输入各事件（ 事件开始点（弧头）事件结束点（弧尾） ）和事件持续时间（权值）.\n格式：事件开始点，事件结束点，时间持续时间:\n“）;
 printf（“例如:121\n     232\n     342\n\n“）;
 printf（“该工程最优规划为:\n“）;
 printf（“\n1->2  1\n2->3  2\n3->4  2\n“）;
 while（j!=‘N‘&&j!=‘n‘）
      {
	   CreateGraph（&G）;          //生成邻接表结构的图
       t=CriticalPath（&G）;    //寻找G的关键路径
       if（t==0） printf（“该工程图有回路!\n“）;
   //若返回为False表明该图存在有环路
       else printf（“\n“）;
       printf（“是否继续新的工程?（Y/N）“）;
       scanf（“ %c“&j）;
     }
}

int CriticalPath（Graph *G）
{                         //G为有向网，输出G的各项关键活动
 int jdutk=0eeel;
 int vl[MAX_VERTEX_NUM]; //存放各顶点的最迟发生时间
 Stack T;     //堆栈T存放拓扑排序的顶点序列
 ArcNode *p;
 Initial（&T）;  //初始化堆栈T
 if（!TopologicalSort（G&T）） return（0）; 
    //利用拓扑排序求出各顶点的最早发生时间，并用T返回拓扑序列，
    //若返回False，表明该网有回路
 printf（“该工程最优规划为:\n\n“）;
 Gettop（&T&k）; //k取得拓扑序列的最后一个顶点，即该网的汇点
 vl[k]=ve[k]; //汇点的vl=ve
 for（j=1;j<=G->vexnum;j++） if（j!=k） vl[j]=INFINITY; //将其他的顶点的vl置为IFINITY
 while（!StackEmpty（&T）） //按拓扑逆序求各顶点的vl值
  {Pop（&T&j）;
   for（p=G->AdjList[j];p;p=p->nextarc）
     {k=p->adjvex;
      dut=p->weight;
      if（vl[k]-dut         //vl的求法：vl（i）=Min{vl（j）-dut（）} ∈Si=n-2...0
     }
  }
 for（j=1;j<=G->vexnum;j++）  //求每条弧的最早开始时间ee和最迟开始时间el
   for（p=G->AdjList[j];p;p=p->nextarc）
      {k=p->adjvex;
       dut=p->weight;
       ee=ve[j];
       el=vl[k]-dut;
       if（ee==el） printf（“%d->%d%5d\n“jkdut）; //若ee=el，则该弧为关键活动
      }
 return（1）;
}
void CreateGraph（Graph *G）//构造邻接表结构的图G
{
 int i;
 int startendarcweight;
 ArcNode *s;
 printf（“\n现在请输入您的项目数和事件数（顶点数，弧数）:“）;
 scanf（“%d%d“&G->vexnum&G->arcnum）; //输入图的顶点数和弧数
 for（i=1;i<=G->vexnum;i++） G->AdjList[i]=NULL; //初始化指针数组
 printf（“请输入各事件（ 事件开始点（弧头）事件结束点（弧尾） ）和事件持续时间（权值）.\n格式：事件开始点，事件结束点，时间持续时间:\n“）

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6225  2009-09-26 12:23  8.c

     文件       3339  2009-09-26 18:25  8.dsp

     文件        510  2009-09-26 18:25  8.dsw

     文件      41984  2009-09-26 18:25  8.ncb

     文件      48640  2009-09-26 18:25  8.opt

     文件        721  2009-09-26 18:25  8.plg

     文件     129536  2009-09-10 15:40  课程设计PPT.ppt

     文件     267776  2009-09-11 20:46  课程设计任务书.doc

     文件      72192  2009-09-10 14:46  流程图.vsd

     文件      31232  2009-09-26 18:31  工程规划题目.doc

     文件      33792  2009-09-26 18:25  Debug\vc60.idb

     文件      53248  2009-09-26 18:25  Debug\vc60.pdb

     文件      13635  2009-09-26 18:25  Debug\8.obj

     文件     189168  2009-09-26 18:25  Debug\8.ilk

     文件     184395  2009-09-26 18:25  Debug\8.exe

     文件     451584  2009-09-26 18:25  Debug\8.pdb

     文件     177584  2009-09-26 18:25  Debug\8.pch

     目录          0  2009-09-26 12:23  Debug

----------- ---------  ---------- -----  ----

              1705561                    18