当前位置：首页 > 编程日记 > 正文

【数据结构】关键路径

编程日记 2024-10-16 07:10:00

在有向图中，如果用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间，这样的活动称为边表示活动的网，简称AOE网（Activity On Edge）。通常可以用AOE网来估算工程的完成时间，他不仅表达了工程中各事件的先后关系，更可说明整个工程至少需要多少时间完成以及哪些活动是影响工程进度的关键活动。

在AOE网中：

源点：一个入度为零的事件

汇点：一个出度为零的事件

由于一个AOE网中某些活动可以并行地进行，所以完成的工程的最短时间是从源点到汇点最长路径的长度。相应地，从源点到汇点的最长路径称为AOE网的关键路径。

AOE网的创建以及求出各事件的最早发生时间和各事件的最晚允许开始时间

$e(i)$ ：活动 $a_{i}$ 的最早开始时间

$l(i)$ ：活动最迟开始时间，这是在不推迟整个工程完成的前提下，活动 $a_{i}$ 最迟必须开始的时间。

若某一活动 $a_{i}$ 最早开始时间 $e(i)$ 等于这个活动的最迟开始时间 $l(i)$ ，则说明 $a_{i}$ 是一个关键活动。

文件直接读取数据！！！！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>const int M = 20;
int ve[M];//事件最早发生时间向量
int seq[M];//拓扑排序列向量
int vl[M];//事件最晚允许发生时间向量
int e[M];//活动的最早开始时间
int l[M];//活动最迟开始时间typedef struct node//边结点类型定义
{int adjvex;int len;struct node *next;
}EdgeNode;typedef struct de //带顶点入度的头节点定义
{EdgeNode *FirstEdge;char vertex;int id;
}vertexnode;typedef struct 
{vertexnode adjlist[M];int n,e;
}AoeGraph;void creat (AoeGraph *g)
{int i,j,k,len;EdgeNode *s;FILE *f;f=fopen("test.txt","r");fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s %d",&g->adjlist[i].vertex,&g->adjlist[i].id);g->adjlist[i].FirstEdge=NULL;}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&len);s=(EdgeNode*)malloc(sizeof(EdgeNode));s->len=len;s->adjvex=j;s->next=g->adjlist[i].FirstEdge;g->adjlist[i].FirstEdge=s;}return ;
}void print(AoeGraph g)
{EdgeNode *p;int i;printf("一共有%d个结点，%d条边\n",g.n,g.e);for(i=0;i<g.n;i++){printf("入度：%d  V%c ",g.adjlist[i].id,g.adjlist[i].vertex);p=g.adjlist[i].FirstEdge;while(p){printf("(w=%d) %d",p->len,p->adjvex);if(p->next)printf(" -> ");p=p->next;}printf("\n");}return ;
}//求每个事件最早发生的时间
int EarlistTime(AoeGraph gout)//返回输出的顶点个数
{int count=0,i,j,v,flag[M];int queue[M];int front = 0,rear = 0;EdgeNode *p;memset(ve,0,sizeof(ve));//初始化每个顶点最早开始时间是ve[i]=0;memset(flag,0,sizeof(flag));//访问标记初始化for(i=0;i< gout.n;i++){if(gout.adjlist[i].id==0 && flag[i]==0){queue[rear++]=i;flag[i]=1;}}while(front < rear)//队列不为空{v=queue[front++];//队首元出队printf("%c ",gout.adjlist[v].vertex);seq[count++]=v;//记录拓扑排序当前元素，计数器加一p=gout.adjlist[v].FirstEdge;while(p){j=p->adjvex;if(--gout.adjlist[j].id==0 && flag[j]==0)//入度为0则将进队{queue[rear++]=j;flag[j]=1;}if(p->len+ve[v]>ve[j])ve[j]=ve[v]+p->len;p=p->next;}}printf("\n各个事件的最早发生时间：\n");for(i=0;i<gout.n;i++){printf("ve[%d]=%d\n",i,ve[i]);}return count;
}//各事件的最晚允许开始时间
void LateTime(AoeGraph gin)
{int k=gin.n-1,i,j,v;EdgeNode *p;for(i=0;i<gin.n;i++)vl[i]=ve[seq[gin.n-1]];while(k>-1)//按照拓扑排序求各事件最晚时间{v=seq[k];p=gin.adjlist[v].FirstEdge;while(p){j=p->adjvex;if(vl[j]-p->len < vl[v])vl[v]=vl[j]-p->len;p=p->next;}k--;}printf("各个事件允许发生的最晚时间：\n");for(i=0;i<gin.n;i++){printf("vl[%d]=%d\n",i,vl[i]);}return ;
}//求e[k] 和 l[k]
void activity(AoeGraph g)
{int i,j,k,q;EdgeNode *p; memset(e,0,sizeof(e));i=0;q=0;printf("--------------------------------------------------------------------------\n");printf("起点 | 终点 | 活动最早开始时间 | 活动最晚开始时间 | 差值 | 是否为关键路径|\n");for(j=0;j<g.n;j++){p=g.adjlist[j].FirstEdge;while(p){k=p->adjvex;e[i]=ve[j];l[i]=vl[k]-p->len;printf("%c    |%5d |%10d        |%10d        |%5d |",g.adjlist[j].vertex,k,e[i],l[i],l[i]-e[i]);if(e[i]==l[i]){printf("    √\n");}else{printf("    \n");}printf("--------------------------------------------------------------------------\n");p=p->next;}}
}int main ()
{AoeGraph g;creat(&g);print(g);printf("\n输出的顶点个数：%d\n\n",EarlistTime(g));LateTime(g);activity(g);return 0;
}

https://www.dkcj.cn/info/23260.html

呼伦湖国家级自然保护区管理局投放草料保野生黄羊过冬

图为保护区工作人员正在观测黄羊的生活轨迹并记录数据。王艳清摄图为保护区工作人员正在观测黄羊的生活轨迹并记录数据。王艳清摄中新网呼伦贝尔1月16日电 (记者李爱平)中国北方正是最为寒冷的时节，呼伦湖国家级自然保护区管理局内的60只野生黄羊正在面临食草…

编程日记2024/10/16 07:00:00

buildroot httpd php

/********************************************************************* buildroot httpd php* 说明：* 在buildroot中选择了php，但是在测试的时候发现总是出现下面这行* 错误，库是存在的，但是却没有放对…

编程日记2024/10/16 06:50:00

VS快速注释多行以及取消

快速注释多行：Ctrl K 然后 Ctrl C 快速取消多行注释 ：Ctrl K 然后 Ctrl U

编程日记2024/10/16 06:40:00

前端的一些小的效果

1 . 移动端字体自适应大小（暂时没用过，不过据说很有用也很好用） body{font-family: "Microsoft YaHei";font-size: 0.14rem;color: #666;max-width: 640px;margin: auto;}media screen and (min-width: 360px) { html {font-s…

编程日记2024/10/16 06:30:00

Java虚拟机规范阅读(二)IEEE754简介以及Java虚拟机中的浮点算法

什么是浮点数在计算机系统的发展过程中，曾经提出过多种方法表达实数。典型的比如相对于浮点数的定点数（Fixed Point Number）。在这种表达方式中，小数点固定的位于实数所有数字中间的某个位置。货币的表达就可以使用这种方式&#…

编程日记2024/10/16 06:20:00

【ACM】杭电OJ 5055（Bob and math problem）

http://acm.hdu.edu.cn/showproblem.php?pid5055 注意几点： 1、全部都是偶数，输出-1 2、n-1个是0，第n个不论是奇数，还是偶数，输出-1 3、n1的情况 4、将所有数字从大到小排列，挑出最小的奇数放在最后…

编程日记2024/10/16 06:10:00

每天工作4小时的程序员【转】

每个人都熟悉这种作息规律：早上9点去上班，坐在电脑前面，编一天的程序，下午5点下班回家。如今，非常感谢蒂莫西费里斯 (Timothy Ferriss)的《每周工作4小时》，我开始重新思考应该如何工作，如何让自…

编程日记2024/10/16 06:00:00

ARKIT/ARCore对比分析(一)

ARKit简介 ARkit是什么？ 苹果为什么发布ARkit？（6月5日的苹果WWDC 2017全球开发者大会上，苹果发布了AR开发平台ARkit） 1.概述：ARkit应用平台是苹果的首个 AR 产品。iOS 11引入了ARKit应用平台，…

编程日记2024/10/16 05:50:00

每个程序员必看：如何在40岁后继续做软件开发？

导读: 这是一个 42 岁的开发者所写经验分享文章．并且列出一些他 18 年多身为软件开发者的经验谈．许多部分看完后都会希望自己当时就能够了解，所以很推荐不论是新手或是老手都要好好阅读这一篇文章。故事很长，一切从 1997 年开始讲…

编程日记2024/10/16 05:40:00

【ACM】杭电OJ 1009 （FatMouse' Trade）。

两个条件貌似缺一不可不明白为什么不能是sum（s[i].value*s[i].cat_food）； #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int maxn 1010;typedef …

编程日记2024/10/16 05:30:00

Java图形化：布局方式

布局方式 FlowLayout:流布局 BorderLayout:边框布局 GridLayout:网格布局FlowLayout（流布局） 像Word打字，组件从左向右排列，一列排满后自动换下一行。组件默认居中对齐，可以设置左/右对齐。流布局会维持组件的原始大小…

编程日记2024/10/16 05:20:00

ARKIT/ARCore对比分析(二)

ARKit(2) ARCore 和 ARKit平台特点比对曾与一家最大的 IMU OEM 交谈过，为了节省成本，他们的智能机IMU 在工厂中只是在单一温度下进行标定。这意味着 IMU 硬件在某一指定的温度下，误差被调节到最低。但当手机发热的时候，IMU 就不…

编程日记2024/10/16 05:10:00

【ACM】杭电OJ 1789（Doing Homework again）

http://acm.hdu.edu.cn/showproblem.php?pid1789 cmp函数： 先按扣分由多到少进行排序，然后如果遇到扣分一样的，则先做时间少的。 vis数组： 最要的事，放在它的截至日期那一天去做，然后，之后…

编程日记2024/10/16 05:00:00

ARKit 与 ARCore比对（三）

ARKit 和 ARCore剖析、结构、原理介绍 ARKit 和 ARCore 都是三部分：相机姿态估计， 环境感知（平面估计）及光源感知。 ARCore 的部分源码：https://github.com/google-ar/arcore-unity-sdk/tree/master/Assets/GoogleARCo…

编程日记2024/10/16 04:40:00

前端开发之retina屏幕

像素 && ppi 首先先说一下pixel(picture element)，显示图像的最小单位，有多个带色彩的像素点组成的整体就是一张图像。然后再说一下ppi(pixel per inch)这个概念，其实就是在每英寸显示的像素数。设备像素 && 逻辑像素 &…

编程日记2024/10/16 04:30:00

【ACM】Uva 1152 （4 Values whose Sum is 0）二分查找lower_bound() 和upper_bound()的使用

【问题描述】 The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d) ∈ A B C D are such that a b c d 0. In the following, we assume that all lists have the same size n. …

编程日记2024/10/16 04:20:00

广东“基因编辑婴儿事件”调查组：将对贺建奎依法依规严肃处理

雷锋网(公众号：雷锋网)消息，1 月 21 日，新华社报道了关于“基因编辑婴儿事件”的初步调查结果，该结果宣称，该事件是南方科技大学副教授为了追逐个人名利而进行的人类胚胎基因编辑活动；而在此过程中&#xf…

编程日记2024/10/16 04:10:00

测试我的第一个随笔

# encodingutf-8## Python Version 3.5# 利用数学中的复数求解一元一次方程(从网上看来的)def solve(qx, var): qx qx.replace(, -() ) c eval(qx , {var: 1j}) return -c.real/c.imagres solve(2*x 4 8,x)print(res)转载于:https://www.cnblogs.com/imyjy/p/…

编程日记2024/10/16 04:00:00

ubuntu16.04 下安装Opencv2.4.9

ubuntu16.04 下安装Opencv2.4.9 OpenCV的源码download from: https://sourceforge.net/projects/opencvlibrary/?sourcetyp_redirect[plain] view plaincopycd opencv-2.4.9 mkdir build sudo chmod -R 777 build cd build [plain] view plaincopycmake -D CMAKE_…

编程日记2024/10/16 03:50:00

UVa 167（八皇后）、POJ2258 The Settlers of Catan——记两个简单回溯搜索

UVa 167 题意：八行八列的棋盘每行每列都要有一个皇后，每个对角线上最多放一个皇后，让你放八个，使摆放位置上的数字加起来最大。参考：https://blog.csdn.net/xiaoxiede_wo/article/details/79973171 1 #include <io…

编程日记2024/10/16 03:40:00

AR + ROS +UBUNTU16.04+ORB-SLAM2

ORB SLAM2 USB摄像头实验环境ubuntu 16.04ros kinetic OPencv2.4.9 Step1： 配置环境变量 $ mkdir -p ~/catkin_ws/src $ cd ~/catkin_ws/src 在’src’目录中可能没有任何软件包，只有一个CMakeLists.txt，依然可以编译它： …

编程日记2024/10/16 03:30:00

Cross-validation

2019独角兽企业重金招聘Python工程师标准>>> 1: Introduction To Validation So far, weve been evaluating accuracy of trained models on the data the model was trained on. While this is an essential first step, this doesnt tell us much about how well …

编程日记2024/10/16 03:20:00

【ACM】杭电OJ 1877 又一版A+B（进制转换）

注意：A和B都是0的情况 A和B为int也可以AC #include<cstdio> #include <iostream> using namespace std;const int maxn 10000;int a[maxn];int main() {long long A,B;int m,k;while(scanf("%d",&m)!EOF){if(m0) return 0;scanf("…

编程日记2024/10/16 03:10:00

[POI2009]KAM-Pebbles BZOJ1115 [ 待填坑 ] 博弈

有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。感谢MT大牛翻译. Sample OutputNIE…

编程日记2024/10/16 03:00:00

ROS中使用摄像头的问题

ROS中使用摄像头的问题 0.prepare 4 . 安装uvc_cam $ sudo apt-get install ros-indigo-uvc-camera $ source /opt/ros/indigo/setup.bash 采用apt-get的方式，直接装在了ROS的安装路径中，并设置工作路径。安装成功后在/opt/ros/hydro/的路径中就…

编程日记2024/10/16 02:50:00

EmEditor Professional(文本编辑) 下载地址

http://www.greenxf.com/soft/2126.html 16.1.5 http://www.cr173.com/soft/3031.html 16.3.0 http://www.pc6.com/softview/SoftView_43146.html 17.8.1 绿色注册版 EmEditor 71 个实用插件汉化版 http://www.onlinedown.net/soft/35609.htm

编程日记2024/10/16 02:40:00

【ACM】杭电OJ 4548 美素数（二次打表）

二次打表，第一次是标记哪些是素数，哪些不是。第二次是前n个数中 “本身是素数 && 各个位上的和是素数 ” 的个数 TLE： #include <iostream> #include <cstdio> using namespace std;int fun1(int x) {int sum0…

编程日记2024/10/16 02:30:00

animation与transition区别

transition： 过渡属性过渡所需要时间过渡动画函数过渡延迟时间；默认值分别为：all 0 ease 0 1、局限性： 1）只能设置一个属性 2）需要伪类/事件触发才执行 3）只能设置动画初始值和结束值 2、过…

编程日记2024/10/16 02:20:00

如何将cocos2d-x程序分别移植到ios，android，windowsphone三个手机平台上

作者：方格子链接：https://www.zhihu.com/question/21505500/answer/22152464来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。面向android的移植 0. 这移植过程简直…… 1. 完成以上工具的下载安装…

编程日记2024/10/16 02:10:00