include[HTML_REMOVED]

include[HTML_REMOVED]

define MaxVex 100

define MaxInt 32768

using namespace std;

typedef struct EdgeNode{
int adjvex;
int weight;
struct EdgeNode* next;
}EdgeNode;

typedef struct VexNode{
int data;
EdgeNode * firstedge;
}VexNode;

typedef struct{
VexNode vex[MaxVex];
int vexnum,edgenum;
}Adjlist;

typedef struct {
int v0;
int v1;
int weight;
}EdgeInfo;//这个是我用来创建图的数据结构，也是kruskal的辅助数据结构

void create(Adjlist &M,EdgeInfo data[],int n){
for(int i=1;i<=M.vexnum;i) M.vex[i].firstedge=NULL;
for(int i=1;i<=n;i){
int u0=data[i].v0;
int u1=data[i].v1;
EdgeNode p=(EdgeNode )malloc(sizeof(EdgeNode));
//这里还必须要分配空间才能使用
p->adjvex=u1;
p->weight=data[i].weight;
p->next=M.vex[u0].firstedge;
M.vex[u0].firstedge=p;
}
}
//上述实现了构建邻接表
//这里实现拓扑排序
int indegree[MaxVex];
int topo[MaxVex];//这里最好实现一个数组，我们还要判断是否有环
void find_indegree(Adjlist G){
for(int i=1;i<=G.vexnum;i) indegree[i]=0;
for(int i=1;i<=G.vexnum;i){
EdgeNode *p=G.vex[i].firstedge;
while(p!=NULL){
int t=p->adjvex;
indegree[t]++;
p=p->next;
}
}
}

int toposort(Adjlist G,int topo[]){
find_indegree(G);
int stack[MaxVex];
int top=0,toponum=0;//tuponum表示当前tupo序列中有几个结点
for(int i=1;i<=G.vexnum;i){
if(indegree[i]==0){
stack[top]=i;
}
}
while(top>0){
int t=stack[–top];
cout<[HTML_REMOVED]adjvex;
indegree[k]–;
if(indegree[k]==0) stack[top++]=k;
p=p->next;
}
}
if(toponum==G.vexnum){
return 1;
}
return 0;
}
//上述实现了拓扑排序

int ve[MaxVex];//事件的最早开始时间
//所有人到了才能打球事件，所以评估每个人最早出发时间，和路程时间
//最晚到达的那个人，决定了打球时间最早发生时间
int vl[MaxVex];//事件的最晚开始时间
//打球结束这个事件，评估所有人最迟回家时间，和路程时间
//得到每个人最迟出发时间，最早出发的那个人，决定了打球结束事件的时间

//事件是整体安排，活动是个人角度
//最早发生活动，就是我什么时候出发，最早就是能出发就出发
//最晚就是按时到达即可，看要求几点到，我最迟什么时候走
void criticalPath(Adjlist G){
if(toposort(G,topo)==1) cout<<”拓扑完成”<[HTML_REMOVED]adjvex;
if(ve[i]+p->weight>ve[t]){
ve[t]=ve[i]+p->weight;
}//我来的时间要晚，打球整体向后拖
p=p->next;
}
}
cout<<”ve:”<<’ ‘;
for(int i=1;i<=G.vexnum;i) cout<[HTML_REMOVED]=0;j–){
int i=topo[j];//倒着根据拓扑序列来
EdgeNode * p=G.vex[i].firstedge;
while(p!=NULL){
int t=p->adjvex;
if(vl[i]>vl[t]-p->weight){
vl[i]=vl[t]-p->weight;
}//评估所有人最迟回家时间
p=p->next;
}
}
cout<<”vl:”<<’ ‘;
for(int i=1;i<=G.vexnum;i) cout<[HTML_REMOVED]adjvex;
e=ve[i];l=vl[t]-p->weight;
u=l-e;
if(u==0){
cout<[HTML_REMOVED]next;
}
}
}

int main(){
Adjlist G;
G.vexnum=6,G.edgenum=8;
EdgeInfo data[]={{0,0,0},{1,2,3},{1,3,2},{2,5,3},{2,4,2},{3,4,4},{3,6,3},
{4,6,2},{5,6,1}};
Adjlist &M=G;
create(M,data,8);
// for(int i=1;i<=G.vexnum;i++){
// EdgeNode* p=G.vex[i].firstedge;
// while(p!=NULL){
// cout<[HTML_REMOVED]adjvex<<’ ‘;
// p=p->next;
// }
// cout<<endl;
// }
//完美构建邻接表
criticalPath(G);
}