精华内容
下载资源
问答
  • aoe网关键路径

    2019-11-27 23:19:26
    求出所给的AOE-关键路径。 输入 若干行整数,第一行有2个数,分别为顶点数v和弧数a,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点编号和弧的权值 输出 若干个空格隔开的顶点构成的序列(用小写...

    3:求关键路径

    总时间限制: 

    10000ms

     

    单个测试点时间限制: 

    1000ms

     

    内存限制: 

    65536kB

    描述

    求出所给的AOE-网的关键路径。

    输入

    若干行整数,第一行有2个数,分别为顶点数v和弧数a,接下来有a行,每一行有3个数,分别是该条弧所关联的两个顶点编号和弧的权值

    输出

    若干个空格隔开的顶点构成的序列(用小写字母)

     

    这个题tm坑死我了,没看清题意题意说的是让你输出节点,我给他把边的编号输出了哎呀呀太傻了 我看了一天愣是没找到啥致命错误,这个眼睛呀!!!

    #include <bits/stdc++.h>
    using namespace std;
    vector<int>v[2000],ans,p[2000];
    int deg[2000],vl[1000],ve[1000],v1[1000],e[1000];
    struct asd{
        int x,y,z;
    }ee[1000];
    int q[1000][1000];
    priority_queue<int,vector<int>,greater<int> >ann;
    bool vee[10000];
    int n,m;
    int main(){
    
        while(cin>>n>>m){
            memset(deg,0,sizeof(deg));
            for(int i=1;i<=m;i++)
            {
                int a,b,c;
                cin>>a>>b>>c;
                ee[i].x=a,ee[i].y=b,ee[i].z=c;
                q[a][b]=c;
                v[a].push_back(b);
                p[b].push_back(a);
                deg[b]++;
            }
    
            for(int i=1;i<=n;i++){
                if(deg[i]==0)
                {
                    ann.push(i);
                }
            }
    
            memset(vl,0,sizeof(vl));
            while(ann.size()){
                int t=ann.top();
                ann.pop();
                ans.push_back(t);
                for(int i=0;i<v[t].size();i++)
                {
                    int y=v[t][i];
                    deg[y]--;
                    if(deg[y]==0){
                        ann.push(y);
                    }
                    vl[y]=max(vl[y],vl[t]+q[t][y]);
                }
            }
            if(ans.size()<n)
                continue;
            memset(ve,0x3f3f3f3f,sizeof(ve));
            ve[ans[n-1]]=vl[ans[n-1]];
            for(int j=n-1;j>=0;j--){
                int xx=ans[j];
                for(int i=0;i<p[xx].size();i++)
                {
                    int y=p[xx][i];
                    ve[y]=min(ve[y],ve[xx]-q[y][xx]);
                }
            }
            ans.clear();
            memset(vee,false,sizeof(vee));
            for(int i=1;i<=m;i++){
                int x=ee[i].x,y=ee[i].y,z=ee[i].z;
                e[i]=vl[x];
                v1[i]=ve[y]-z;
                //cout<<v1[i]<<' '<<e[i]<<endl;
                if(v1[i]==e[i]){
                    if(!vee[x])
                    {
                        cout<<'v'<<x<<' ';
                        vee[x]=1;
                    }
                    if(!vee[y])
                    {
                        vee[y]=1;
                        cout<<'v'<<y<<' ';
                    }
                }
            }
            cout<<endl;
        }
    }

     

    展开全文
  • 教你轻松计算AOE网关键路径

    万次阅读 多人点赞 2018-09-19 16:14:23
    转:教你轻松计算AOE网关键路径 认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV的边上加上...

    转:教你轻松计算AOE网关键路径

    认识AOE网

      有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

      在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE网,如下图: 

     

      

     

     

      图中,顶点表示事件(能被触发,两特征属性:最早发生时间Ve(j);最晚发生时间Vl(j)),边表示活动(能被开始,两特征属性:最早开始时间e(i);最晚开始时间l(i)),权表示活动持续时间,通常用AOE网来估算工程完成的时间

     

    两条原则:

      Ø  只有某顶点所代表的事件发生后,从该顶点出发的各活动才能开始

      Ø  只有进入某顶点的各活动都结束,该顶点所代表的事件才能发生

     

    计算关键路径

      首先,在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。

    计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。

      先来看看四个特征属性的含义:

      Ø Ve(j):是指从始点开始到顶点Vk的最大路径长度

     

       计算技巧:

       (1)从前向后,取大值:直接前驱结点的Ve(j)+到达边(指向顶点的边)的权值,有多个值的取较大者

       (2)首结点Ve(j)已知,为0

     

      如上图各顶点(事件)的Ve(j): (从V1开始)

           V1 :天然是0

           V2:a1边    3

           V3:a3边    2

            V4:分三种情况①a1 + a5 = 5    ②a2 = 6   ③a3 + a6 = 3  取最大者

            V5:........

            V6:........

     

      

     

     

      Ø  Vl(j):在不推迟整个工期的前提下,事件vk允许的最晚发生时间

     

       计算技巧:

       (1)从后向前,取小值:直接后继结点的Vl(j) –发出边(从顶点发出的边)的权值,有多个值的取较小者;

       (2)终结点Vl(j)已知,等于它的Ve(j))

     

      如上图各顶点(事件)的Vl(j): (从V7开始,它的最早、最晚发生时间相同,都为10):

           

           V7:天然等于最大路径长度 10

           V6:由V7 = 10   有 10 - a10 = 6

           V5:由V7 = 10   有10 - a9 = 7

           V4:由V5 = 7       有7 - a8 = 6

           V3:有两个后继 V4和V6,所以分两种情况①V4 - a6 = 5      ②V6 - a7 = 3   取最小者, 所以V3 = 3

           V2:........    

      

     

     

      Ø  e(i): 若活动ai由弧<vk,vj>表示,则活动ai的最早开始时间应该等于事件vk的最早发生时间。因而,有:e[i]=ve[k];(即:边(活动)的最早开始时间等于,它的发出顶点的最早发生时间)

    如上图各边(活动)的e(i):

           活动发生最早时间看的是活动边的前驱节点

          a1    a2   a3 前驱节点都是V1   然后从第一个图中,即最早发生事件中取值  a1= 0   a2 = 0  a3 = 0

          a4 前驱节点是V2     所以有a4 = 3

          a5.....

          a6......

      

     

     

      Ø  l(i): 若活动ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。 因而有:l[i]=vl[j]-len<vk,vj>1(为边(活动)的到达顶点的最晚发生时间减去边的权值

    如上图各边(活动)的l(i):

          活动的最晚发生时间 等于事件的最晚发生时间(第二个图)减去活动边

          即活动边的后继,去图2中找,然后减去活动边

         a4活动边后继是V5   由最晚发生事件得   V5 - a4 = 7 - 4 = 3

      

     

     

      至此已介绍完了四个特征属性的求法,也求出了上图中边的e(i)和l(i),取出e(i)=l(i)的边为a1、a2、a4、a8、a9,即为关键路径上的边,所以关键路径有两条:a1 a4 a9和 a2 a8 a9

     

      

     

     

    ==========================================================================

     

    第二个例子对比一下

       

    (最早发生,从前往后算;最迟发生,从后往前算。)

    总结

      求关键路径,只需理解顶点(事件)和边(活动)各自的两个特征属性以及求法即可:

       Ø  先根据首结点的Ve(j)=0由前向后计算各顶点的最早发生时间

       Ø  再根据终结点的Vl(j)等于它的Ve(j)由后向前依次求解各顶点的最晚发生时间

       Ø  根据边的e(i)等于它的发出顶点的Ve(j)计算各边的最早开始时间(最早开始,对应最早发生)

       Ø  根据边的l(i)等于它的到达顶点的Vl(j)减去边的权值计算各边的最晚开始时间(最晚开始,对应最晚发生)

    展开全文
  • AOE网关键路径求解例题 三道 首先明确顶点是事件,边是活动。 1 2 3 解题技巧: 先求Ve 从前往后推,取活动之和最大的 作为顶点(事件)最早发生时间; 求Vl 通过Ve知道最后汇点的最晚发生时间(和汇点的最...

    AOE网关键路径求解例题 三道

    首先明确顶点是事件,边是活动。

    1

    在这里插入图片描述

    在这里插入图片描述


    2

    在这里插入图片描述
    在这里插入图片描述


    3

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    解题技巧:

    先求Ve 从前往后推,取活动之和最大的 作为顶点(事件)最早发生时间;
    求Vl 通过Ve知道最后汇点的最晚发生时间(和汇点的最早发生时间相等),从后往前推,用顶点和活动做差取结果最小 作为顶点最晚发生时间。这里典型的例子就是V4,应该用V6的最晚发生时间减去a9和a6而不是直接减去a7,因为V6-a7 = 10 > 7 ,而我们要的是所有可能中最小的值,和求Ve时候相反。
    接着求e活动的最早发生时间,这个通过Ve可以得到,例如a5活动的最早发生时间其实就是V2的最早发生时间,也就是等于4.
    求l活动的最晚发生时间,通过Vl可得,这里需要注意的是从后往前推,例如,a10的最晚发生时间等于V6的最晚发生时间减去a10所需要花费的时间4, 14 - 4 = 10;a4的最晚发生时间就是V4的最晚发生时间-a4 = 7- 5 = 2;

    最后找到e == l的那几个关键活动,那么关键路径就是这些关键路径按顺序连起来的顶点了,当然关键路径可能有多条,由关键活动决定。

    展开全文
  • AOE网络关键路径

    2012-07-09 02:54:44
    用C++实现的代码,求AOE网络的关键路径,有详细注释
  • C语言求AOE网关键路径

    2010-05-24 16:03:07
    这个程序为实现AOE关键路径的程序,工具为VC,语言为C,内有readme,
  • 邻接矩阵、邻接表中任选一种作为图的存储结构,AOE网关键路径算法,实现从AOE网源点到汇点的关键路径(2学时) 三、算法思路分析 四、算法反思 五、代码实现 #include<stdio.h> #include<stdlib.h> #...

    一、基础知识

    二、代码要求

    邻接矩阵、邻接表中任选一种作为图的存储结构,AOE网关键路径算法,实现从AOE网源点到汇点的关键路径(2学时)

    三、算法思路分析

    四、算法反思

    五、代码实现

    #include<stdio.h>
    #include<stdlib.h>
    #define MaxVertexNum 100
    typedef char VertexType;
    typedef int EdgeType;
    
    /*图的邻接表存储结构*/
    typedef struct node//边表结点 
    {
    	int adjvex;					//邻接点域 
    	struct node *next;			//指向下一个邻接点的指针域
    	int info;	//若要表示边上的权值信息,则应增加一个数据域info 
    }EdgeNode;
    typedef struct vnode//表头结点 
    {
    	VertexType vertex;			//顶点域 
    	EdgeNode *firstedge;		//边表头指针 
    }VertexNode;
    typedef struct
    {
    	VertexNode adjlist[MaxVertexNum];//邻接表 
    	int n,e;						//顶点数和边数 
    }ALGraph;//以邻接表方式存储的图类型 
    
    int visited[MaxVertexNum];
    
    void CreateALGraph(ALGraph *G)//有向图的邻接表存储的算法 
    {
    	int i, j, k, weight;
    	EdgeNode *s;
    	printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    	scanf("%d,%d",&(G->n),&(G->e));		//读入顶点数和边数
    //	printf("%d,%d",(G->n),(G->e));
    	printf("请输入顶点信息(输入格式为:<回车>顶点号):\n");
    	for(i=0; i<G->n; i++)
    	{
    		scanf("\n%c",&(G->adjlist[i].vertex));//读入顶点信息 
    		G->adjlist[i].firstedge=NULL;//定点的边表头指针设为空 
    	}
    	printf("请输入边的信息(输入格式为:i,j,weight):\n");
    	for(k=0; k<G->e; k++)//建立边表 
    	{
    		scanf("%d,%d,%d",&i,&j,&weight);//读入边<Vi,Vj>的顶点对应序号 
    		s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成新表边结点s 
    		s->adjvex=j;//邻结点序号为j 
    		s->info=weight;
    		s->next=G->adjlist[i].firstedge;//将新表边结点s插入到顶点为Vi的边表头部,在录入的时候,只要i没改变,也就是起始顶点没改变就是在一行的 
    		G->adjlist[i].firstedge=s;
    	}
    }
    
    void CriticalPath(ALGraph *G)
    {
    	int i,j,k,e,l;
    	int ve[MaxVertexNum],vl[MaxVertexNum];//建立ve,vl数组 
    	EdgeNode *p;
    	for(i=0; i<G->n; i++)					//初始化ve数组 
    		ve[i]=0;
    	for(i=0; i<G->n; i++)					//按拓扑有序求其余各顶点的最早发生时间 
    	{
    		p=G->adjlist[i].firstedge;
    		while(p!=NULL)
    		{
    			k=p->adjvex;
    			if(ve[i]+p->info>ve[k])
    				ve[k]=ve[i]+p->info;
    			p=p->next;
    		}
    	}
    	for(i=0; i<G->n; i++)			//初始化vl数组 
    		vl[i]=ve[G->n-1];
    	for(i=G->n-2; i; i--)			//按逆拓扑有序求其余各顶点的最迟发生时间vl[i] 
    	{
    		p=G->adjlist[i].firstedge;
    		while(p!=NULL)
    		{
    			k=p->adjvex;
    			if(vl[k]-p->info<vl[i])
    				vl[i]=vl[k]-p->info;
    			p=p->next;
    		}
    	}
    	for(i=0; i<G->n; i++)		//根据各顶点的ve和vl值,求出每条边上活动的开始时间e和最迟开始时间l 
    	{
    		p=G->adjlist[i].firstedge;//若某条边满足e==l 
    		while(p!=NULL)//则这条边上的活动为关键活动 
    		{
    			k=p->adjvex;
    			e=ve[i];
    			l=vl[k]-p->info;
    			if(e==l)
    				printf("(%c,%c),e=%d,l=%d\n",G->adjlist[i].vertex,G->adjlist[k].vertex,e,l);
    			p=p->next;
    		}
    	}
    }
    
    int main()
    {
    	ALGraph x;
    	CreateALGraph(&x);
    	CriticalPath(&x);
    	return 0;
    }
    
    /*有错误,从读入顶点数和边数错了。 
    void CreateALGraph(ALGraph *G)//有向图的邻接表存储的算法 
    {
    	int i, j, k, weight;
    	EdgeNode *s;
    	printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    	scanf("%d,%d",&(G->n),&(G->e));		//读入顶点数和边数
    	printf("%d,%d",(G->n),(G->e));
    	printf("请输入顶点信息(输入格式为:<回车>顶点号):\n");
    	for(i=0; i<G->n; i++)
    	{
    		scanf("\n%c",&(G->adjlist[i].vertex));//读入顶点信息 
    		G->adjlist[i].firstedge=NULL;//定点的边表头指针设为空 
    	}
    	printf("请输入边的信息(输入格式为:i,j,weight):\n");
    	for(k=0; k<G->e; k++)//建立边表 
    	{
    		scanf("%d,%d,%d",&i,&j,&weight);//读入边<Vi,Vj>的顶点对应序号 
    		s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成新表边结点s 
    		s->adjvex=j;//邻结点序号为j 
    		s->info=weight;
    		s->next=G->adjlist[i].firstedge;//将新表边结点s插入到顶点为Vi的边表头部,在录入的时候,只要i没改变,也就是起始顶点没改变就是在一行的 
    		G->adjlist[i].firstedge=s;
    	}
    }
    错误原因:这个函数没错,具体错误见10数据结构6-1深度脑残bug2 
    */  
    
    展开全文
  • AOE网关键路径计算

    2019-06-10 09:37:58
    AOE网 若在带权的有向无环图中,以顶点表示事件(event),以有向边表示活动,边上的权值表示活动的开销(时间等),则此带权有向图称为AOE网。...关键路径 从源点到中点的最大路径长度。 如何计算 ...
  • 数据结构课本上的求关键路径的算法,注释详细,应该对着书看都能懂的,基本都是书上的思路
  • 认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV的边上加上权值表示完成该活动所需的时间,则...
  • 在一个有向无环图中,求解关键路径以及其长度。 思路 1.按拓扑排序和逆拓扑排序分别计算各顶点的(事件)的最早发生时间和最迟发生时间。 2.用上面的结果计算各边的(活动)的最早开始时间和最迟开始时间。 3.e[i-&...
  • 一、AOE网的概念 使用有向图来抽象工程,使用节点表示事件,有向边表示活动,边的权值表示活动执行时间,边的方向代表事件触发的先后顺序,这样的有向图称作AOE网,常被用作工程中预计进度。AOE网中入度为0(没有...
  • 认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。  在AOV的边上加上权值表示完成该活动所需的时间,则称...
  • 本次结合系统分析师—运筹方法—网络规划技术—关键路径章节,对原文链接描述不准确的地方做了修正。 认识AOE网  有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV...
  • 先了解一下AOE网关键路径: 如果在有向图中用顶点表示事件,用弧表示活动,用弧上的权表示活动持续时间,称该带权有向图(即有向)为边表示活动的(activity on edge network),简称AOE网。 在AOE网中,只有一个...
  • //遍历拓朴排序后的节点,找出sTime==eTime的节点输出,即为关键路径节点,它们之间的边即为关键路径的活动 Vertex v = sortedVertex.poll(); traversal: while ( true ) { next: for (Edge e : v.edges) ...
  • 图-----------拓扑排序+AOE网络关键路径

    千次阅读 多人点赞 2013-07-20 02:31:30
    )时间,比如上面的红线部分就是完成最大花费时间,关键路径就是这条长度最长的路径(a1->a4->a7->a10或者 a1->a4->a8->a11[关键路径不唯一] ) (2)问题怎么求解? a . 事件(eVent)的最早(Early)发生时间--- 源点到...
  • [百度云盘上的相关工程链接](https://pan.baidu.com/s/1R8DHKU6d851fBdcf_DXehQ "没有提取码")![图片说明](https://img-ask.csdn.net/upload/201912/13/1576240272_388536.png)
  • 【笔记】AOE网关键路径

    万次阅读 多人点赞 2017-12-02 01:06:32
    AOE网 关键路径关键路径的算法实现
  • AOE关键路径

    2015-12-15 11:51:17
    教你轻松计算AOE网关键路径 认识AOE网 有向图中,用顶点表示活动,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。 在AOV的边上加上...
  • AOE_关键路径 源程序

    2009-06-25 15:20:06
    图的应用 关于AOE网关键路径的算法 内容:按照图的“邻接表”存储结构表示AOE网,实现求其关键路径的算法
  • AOE网关键路径

    千次阅读 2018-08-20 10:19:51
      AOE网是以边表示活动的有向无环,在AOE网中,具有最大路径长度的路径称为关键路径关键路径表示完成工程的最短工期。 1.AOE网   AOE网是一个带权的有向无环图。其中用顶点表示事件,弧表示活动,权值表示...
  • 在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,698
精华内容 1,079
关键字:

aoe网关键路径