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

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

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

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

int?ve[MAX_VERTEX_NUM];??//全局變量，存放各頂點(diǎn)的最早發(fā)生時(shí)間
void?CreateGraph（Graph?*G）;????//生成圖的鄰接表
int?CriticalPath（Graph?*G）;????//求圖的關(guān)鍵路徑
int?TopologicalSort（Graph?*GStack?*T）;??//進(jìn)行拓?fù)渑判?br/>void?FindInDegree（Graph?*G）;????//求圖各頂點(diǎn)的入度
void?Initial（Stack?*T）;?????//初始化一個(gè)堆棧
int?Push（Stack?*tint?a）;??//將一個(gè)元素入棧
int?Pop（Stack?*tint?*a）;??//將一個(gè)元素出棧
int?Gettop（Stack?*tint?*a）;?//得到棧頂元素
int?StackEmpty（Stack?*S）;??//判斷堆棧是否為空

void?main（）
{Graph?G;??//采用鄰接表結(jié)構(gòu)的圖
?char?j=‘y‘;
?int?t;
?printf（“\t\t\t\t本程序?yàn)楣こ桃?guī)劃問(wèn)題.\n“）;
?printf（“首先輸入工程的項(xiàng)目數(shù)（頂點(diǎn)數(shù)）和事件數(shù)（弧數(shù)）.\n格式為：項(xiàng)目數(shù)，事件數(shù)；\n“）;
?printf（“例如：43\n\n“）;
?printf（“接著請(qǐng)輸入各事件（?事件開(kāi)始點(diǎn)（弧頭）事件結(jié)束點(diǎn)（弧尾）?）和事件持續(xù)時(shí)間（權(quán)值）.\n格式：事件開(kāi)始點(diǎn)，事件結(jié)束點(diǎn)，時(shí)間持續(xù)時(shí)間:\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）;??????????//生成鄰接表結(jié)構(gòu)的圖
???????t=CriticalPath（&G）;????//尋找G的關(guān)鍵路徑
???????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的各項(xiàng)關(guān)鍵活動(dòng)
?int?jdutk=0eeel;
?int?vl[MAX_VERTEX_NUM];?//存放各頂點(diǎn)的最遲發(fā)生時(shí)間
?Stack?T;?????//堆棧T存放拓?fù)渑判虻捻旤c(diǎn)序列
?ArcNode?*p;
?Initial（&T）;??//初始化堆棧T
?if（!TopologicalSort（G&T））?return（0）;?
????//利用拓?fù)渑判蚯蟪龈黜旤c(diǎn)的最早發(fā)生時(shí)間，并用T返回拓?fù)湫蛄校?br/>????//若返回False，表明該網(wǎng)有回路
?printf（“該工程最優(yōu)規(guī)劃為:\n\n“）;
?Gettop（&T&k）;?//k取得拓?fù)湫蛄械淖詈笠粋€(gè)頂點(diǎn)，即該網(wǎng)的匯點(diǎn)
?vl[k]=ve[k];?//匯點(diǎn)的vl=ve
?for（j=1;j<=G->vexnum;j++）?if（j!=k）?vl[j]=INFINITY;?//將其他的頂點(diǎn)的vl置為IFINITY
?while（!StackEmpty（&T））?//按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的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++）??//求每條弧的最早開(kāi)始時(shí)間ee和最遲開(kāi)始時(shí)間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，則該弧為關(guān)鍵活動(dòng)
??????}
?return（1）;
}
void?CreateGraph（Graph?*G）//構(gòu)造鄰接表結(jié)構(gòu)的圖G
{
?int?i;
?int?startendarcweight;
?ArcNode?*s;
?printf（“\n現(xiàn)在請(qǐng)輸入您的項(xiàng)目數(shù)和事件數(shù)（頂點(diǎn)數(shù)，弧數(shù)）:“）;
?scanf（“%d%d“&G->vexnum&G->arcnum）;?//輸入圖的頂點(diǎn)數(shù)和弧數(shù)
?for（i=1;i<=G->vexnum;i++）?G->AdjList[i]=NULL;?//初始化指針數(shù)組
?printf（“請(qǐng)輸入各事件（?事件開(kāi)始點(diǎn)（弧頭）事件結(jié)束點(diǎn)（弧尾）?）和事件持續(xù)時(shí)間（權(quán)值）.\n格式：事件開(kāi)始點(diǎn)，事件結(jié)束點(diǎn)，時(shí)間持續(xù)時(shí)間:\n“）