鞍山网站建设联系方式,哪些网站可以做任务挣钱,网站建设相关法律规定,常用的软件开发文档AOE网
用顶点表示事件#xff0c;弧表示活动#xff0c;弧的权表示活动持续时间
关键路径
从源点#xff08;入度为0#xff09;到汇点#xff08;出度为0#xff09;最长的路径
路径长度
路径上各活动持续时间之和#xff08;权值之和#xff09;
求解关键路径 …AOE网
用顶点表示事件弧表示活动弧的权表示活动持续时间
关键路径
从源点入度为0到汇点出度为0最长的路径
路径长度
路径上各活动持续时间之和权值之和
求解关键路径
1、首先需要定义四个描述量 ve(j) : 表示事件 j (用顶点表示 最早发生时间 例如 ve(v1)0, ve(v2)30
vl(j) : 表示事件j的最迟发生时间
vl(v4) 165
e(i) 表示活动用弧表示最早开始时间 e(a3)30
l(i) 表示活动开始的最迟时间
l(a3)120
完成活动ai 的时间余量
l(i) - e(i)
关键活动
关键路径上的活动即l(i)e(i) 的活动
2、如何找l(i)e(i) 的关键活动
设活动ai 用弧j,k表示其持续时间记为 w e(i) ve(i) ; l(i) vl(k) - w;
ve(i) max{ ve(j) w }
vl(i) min{ vl(k) - w }
步骤
1.首先进行拓扑排序
2.根据拓扑排序的顺序求vi和vl
3.求l和e
下面是代码没有检测正确性 #includeiostream
#includemap
#includequeue
#includealgorithm
#includecstring
#includevector
using namespace std;
int n,m;
vectorint v[120];
queueint q;
//邻接表
struct Edge{int to,dis,next;//next用来存储i顶点的其他边的编号
}e[1000];
int head[1000];//用来存储i顶点出现的最后一条边的编号
int num;//边的编号
void add(int from,int to,int dis){e[num].nexthead[from];e[num].toto;e[num].disdis;head[from]num;//对i顶点的最新出现所在边的编号更新
}
//拓扑排序
int indre[1000];
int top[1000],cnt;
void toposort(){for(int i1;in;i){if(indre[i]0)q.push(i);}while(!q.empty()){int kq.front();q.pop();top[cnt]k;for(int ihead[k];i!0;ie[i].next){--indre[e[i].to];if(indre[e[i].to]0)q.push(e[i].to);}}
}
int ve[1000];
int vl[1000];
void keypath(){//*******求所有点的ve********** for(int i1;in;i){int ktop[i];//依次更新与k的所有邻接顶点的最早发生时间 for(int jhead[k];j!0;je[j].next){int pe[j].to;int we[j].dis;if(ve[p]ve[k]w)ve[p]ve[k]w;}}//初始化所有点的vl for(int i1;in;i){vl[i]ve[n];} //**********求所有点的vl***** for(int in;i1;i){int ktop[i];for(int jhead[j];j!0;je[j].next){int pe[j].to;int we[j].dis;if(vl[k]vl[p]-w)vl[k]vl[k]-w;}}//******求出关键活动******for(int i1;in;i){for(int jhead[i];j!0;je[i].next){int pe[j].to;int we[j].dis;int lvl[j]-w;//求l if(lve[i])couti-pendl;//输出关键活动 }}
}
int main(){cinnm;for(int i1;im;i){int x,y,v;cinxyv;add(x,y,v);indre[y];}toposort();keypath();return 0;
}
