#include?
#include?
#define?MAX_VERTEX_NUM?30?//圖的最大頂點數(shù)
#define?MAX?30????????????//棧的最大容量
#define?INFINITY?30000;???//定義最大的最遲發(fā)生時間

typedef?struct?ArcNode
{int?adjvex;??????????????//該弧所指向的頂點的位置
?int?weight;??????????????//該弧所代表的活動的持續(xù)時間
?struct?ArcNode?*nextarc;?//指向下一條弧的指針
}ArcNode;???????//弧結點

typedef?struct
{int?indegree[MAX_VERTEX_NUM];?//存放各頂點的入度
?ArcNode*?AdjList[MAX_VERTEX_NUM];?//指向第一條依附該頂點的弧的指針
?int?vexnumarcnum;????????????????//圖的當前頂點和弧數(shù)
}Graph;

typedef?struct????//定義堆棧結構
{int?elem[MAX];???//棧區(qū)
?int?top;?????????//棧頂指針
}Stack;

int?ve[MAX_VERTEX_NUM];??//全局變量，存放各頂點的最早發(fā)生時間
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本程序為工程規(guī)劃問題.\n“）;
?printf（“首先輸入工程的項目數(shù)（頂點數(shù)）和事件數(shù)（弧數(shù)）.\n格式為：項目數(shù)，事件數(shù)；\n“）;
?printf（“例如：43\n\n“）;
?printf（“接著請輸入各事件（?事件開始點（弧頭）事件結束點（弧尾）?）和事件持續(xù)時間（權值）.\n格式：事件開始點，事件結束點，時間持續(xù)時間:\n“）;
?printf（“例如:121\n?????232\n?????342\n\n“）;
?printf（“該工程最優(yōu)規(guī)劃為:\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表明該圖存在有環(huán)路
???????else?printf（“\n“）;
???????printf（“是否繼續(xù)新的工程?（Y/N）“）;
???????scanf（“?%c“&j）;
?????}
}

int?CriticalPath（Graph?*G）
{?????????????????????????//G為有向網(wǎng)，輸出G的各項關鍵活動
?int?jdutk=0eeel;
?int?vl[MAX_VERTEX_NUM];?//存放各頂點的最遲發(fā)生時間
?Stack?T;?????//堆棧T存放拓撲排序的頂點序列
?ArcNode?*p;
?Initial（&T）;??//初始化堆棧T
?if（!TopologicalSort（G&T））?return（0）;?
????//利用拓撲排序求出各頂點的最早發(fā)生時間，并用T返回拓撲序列，
????//若返回False，表明該網(wǎng)有回路
?printf（“該工程最優(yōu)規(guī)劃為:\n\n“）;
?Gettop（&T&k）;?//k取得拓撲序列的最后一個頂點，即該網(wǎng)的匯點
?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現(xiàn)在請輸入您的項目數(shù)和事件數(shù)（頂點數(shù)，弧數(shù)）:“）;
?scanf（“%d%d“&G->vexnum&G->arcnum）;?//輸入圖的頂點數(shù)和弧數(shù)
?for（i=1;i<=G->vexnum;i++）?G->AdjList[i]=NULL;?//初始化指針數(shù)組
?printf（“請輸入各事件（?事件開始點（弧頭）事件結束點（弧尾）?）和事件持續(xù)時間（權值）.\n格式：事件開始點，事件結束點，時間持續(xù)時間:\n“）