#include <iostream>
#include <stdio.h>
#include <stack>
#include<cstdlib>
using namespace std;
const int MAXSIZE=100;
typedef struct EdgeNode //边表结点
{
int adjvex; //存储该顶点的下标
int weight; //对应弧的权值
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode //顶点表结点
{
int in; //入度
int data; //顶点值
EdgeNode *firstedge; //边表头指针
}VertexNode,AdjList[MAXSIZE];
typedef struct
{
AdjList adjList;//顶点表结点合集数组 //???
int numVertexes,numEdges; //顶点数和边数
}graphAdjList,*GraphAdjList;
int *etv,*ltv; //事件最早发生时间和最迟发生时间数组
int *stack2; //用于逆拓扑排序的栈
int top2; //用于stack2的栈指针
bool TopologicalSort(GraphAdjList &GL)
{
EdgeNode *e;
int k,gettop;
int top=0;
int count=0;
int *stack; //拓扑排序栈
stack=(int *)malloc(GL->numVertexes*sizeof(int));
for (int i=0; i<GL->numVertexes; i++)
{
if(GL->adjList[i].in==0) //入度为0的元素进栈
{
stack[++top]=i;
}
}
top2=0;
etv=(int*)malloc(sizeof(int)*GL->numVertexes);
for (int i=0; i<GL->numVertexes; i++)
{
etv[i]=0; //初始化
}
stack2=(int*)malloc(sizeof(int)*GL->numVertexes);
while (top!=0)
{
gettop=stack[top--];
count++; //元素个数计数，判断是否存在环
stack2[++top2]=gettop; //存入逆拓扑排序栈中
for (e=GL->adjList[gettop].firstedge; e; e=e->next)
{
k=e->adjvex;
if(!(--GL->adjList[k].in))
{
stack[++top]=k;
}
if(etv[gettop]+e->weight>etv[k]) //更新最早发生时间
{
etv[k]=etv[gettop]+e->weight;
}
}
}
if(count<GL->numVertexes)
{
return false;
}
return true;
}
void CriticalPath(GraphAdjList &GL)
{
EdgeNode *e;
int gettop,k;
int ete,lte;
TopologicalSort(GL);
ltv=(int*)malloc(sizeof(int)*GL->numVertexes); //最迟发生时间数组
for (int i=0; i<GL->numVertexes; i++)
{
ltv[i]=etv[stack2[GL->numVertexes]]; //初始化终点的最早发生时间，终点的最早发生时间和最迟发生时间是一致的(终点不一定是n-1，而是拓扑排序的最后一个数)
}
while (top2!=0)
{
gettop=stack2[top2--];
for (e=GL->adjList[gettop].firstedge; e; e=e->next)
{
k=e->adjvex;
if(ltv[k]-e->weight<ltv[gettop]) //更新最迟发生时间
{
ltv[gettop]=ltv[k]-e->weight; //可以达到的最晚时间
}
}
}
for (int j=0; j<GL->numVertexes; j++)
{
for (e=GL->adjList[j].firstedge; e; e=e->next)
{
k=e->adjvex;
ete=etv[j];
lte=ltv[k]-e->weight; //此条路线的最晚时间
if(ete==lte) //判断是否是关键路径
{
printf("%d %d %d\n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
}
}
}
}
void Init(GraphAdjList &GL)
{
GL=(GraphAdjList)malloc(sizeof(graphAdjList));
}
int main()
{
GraphAdjList GL;
EdgeNode *p;
int u,v,w;
Init(GL);
printf("请输入顶点个数和边的个数:");
scanf("%d%d",&GL->numVertexes,&GL->numEdges);
printf("请输入边的顶点，及其权值 u，v，w:\n");
for (int i=0; i<GL->numVertexes; i++)
{
GL->adjList[i].in=0;
GL->adjList[i].data=i;
GL->adjList[i].firstedge=NULL;
}
for (int i=0; i<GL->numEdges; i++)
{
p=(EdgeNode *)malloc(sizeof(EdgeNode));
scanf("%d%d%d",&u,&v,&w);
p->adjvex=v;
p->weight=w;
p->next=GL->adjList[u].firstedge;
GL->adjList[u].firstedge=p;
GL->adjList[v].in++;
}
printf("关键路径及其权值:\n");
printf("-----\n");
CriticalPath(GL);
return 0;
}
