PTA How Long Does It Take 思路分析及代码解析

2024-03-29 14:32
文章标签 分析 代码 解析 long 思路 pta take

本文主要是介绍PTA How Long Does It Take 思路分析及代码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PTA How Long Does It Take 思路分析及代码解析v0.9.1

  • 一、前导
    • 1. 需要掌握的知识
    • 2. 题目信息
  • 二、解题思路分析
    • 1. 题意理解
      • 1. 1 输入数据
      • 1.2 输出数据
    • 2. 思路分析（重点）
  • 三、具体实现
    • 1. 弯路和bug
    • 2. 代码框架（重点）
      • 2.1 采用的数据结构
      • 2.2 程序主体框架
      • 2.3 各分支函数
    • 3. 完整AC编码
  • 四、参考

一、前导

1. 需要掌握的知识

  1. AOV网：顶点表示活动，边表示活动间先后关系的有向图 称做 顶点活动网络(Activity On Vertex network)，简称AOV网
  2. 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列 称为 拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做 拓扑排序(Topological sort)。
  3. AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
  4. AOV网构造出拓扑序列的实际意义：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。示例：某专业学生的排课
  5. 拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止
    (1) 选择一个入度为0的顶点并输出
    (2) 从AOV网中删除此顶点及所有出边
    循环结束后，若输出的顶点数 < AOV网中的顶点数，则说明图中存在回路，不存在拓扑序列；若相等，输出的顶点序列就是一种拓扑序列

2. 题目信息

  1. 题目来源：PTA / 拼题A
  2. 题目地址：How Long Does It Take

二、解题思路分析

1. 题意理解

  1. 拓扑排序相关问题

1. 1 输入数据

9 12  //图的顶点数和边数,顶点数最大值100,顶点从0开始编号
0 1 6 //边的两个顶点及其权重, 有向图 0-->1
0 2 4
...
7 8 4

1.2 输出数据

  1. 打印最早完成时间；图如果存在回路，打印 ‘Impossible’

2. 思路分析（重点）

  1. 拓扑排序相关问题：判断图中是否存在回路 + 计算出最早完成时间(不严谨的表述就是：边的权值之和的最大值)

三、具体实现

1. 弯路和bug

  1. 使用指针变量时，先申请内存空间，然后再使用
ptrAdjNode N;
N=(ptrAdjNode)malloc(sizeof(struct AdjNodeStructure));

2. 代码框架（重点）

2.1 采用的数据结构

  1. 使用邻接表存储图：图结构如下所示
typedef int vertex;
typedef int wightType;
#define max 100struct EdgeStruc  //边结构
{vertex V1;vertex V2;wightType weight;
};
typedef struct EdgeStruc *ptrEdge; typedef struct AdjNodeStructure *ptrAdjNode;
struct AdjNodeStructure //图顶点的邻接点
{vertex vertexIndex;wightType weight;ptrAdjNode next;
};struct HeadNode //邻接表的头结点
{ptrAdjNode AdjNode;
};
typedef struct HeadNode HeadNodeArray[max];struct GraphStructure //图
{int vertexNumber;int edgeNumber;HeadNodeArray head;
};
typedef struct GraphStructure *ptrGraph;

2.2 程序主体框架

               程序伪码描述
int main()
{	构建图 然后执行拓扑排序即可return 0;
}

2.3 各分支函数

  1. TopSort( )：拓扑排序子函数。拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止
    (1) 选择一个入度为0的顶点并输出
    (2) 从AOV网中删除此顶点及所有出边
    循环结束后，若输出的顶点数 < AOV网中的顶点数，则说明图中存在回路，不存在拓扑序列；若相等，输出的顶点序列就是一种拓扑序列
int TopSort()
{int Indegree[Graph->vertexNumber],cnt=0,front,result=0;vertex V;ptrAdjNode W;queue<vertex> q;/* 初始化入度 */for(V=0;V<Graph->vertexNumber;V++)Indegree[V]=0;/*遍历图 得到Indegree[] */for(V=0;V<Graph->vertexNumber;V++){W=Graph->head[V].AdjNode;while(W){Indegree[W->vertexIndex]++;W=W->next;}		} /*将所有入度为0的顶点入列*/for(V=0;V<Graph->vertexNumber;V++) {if(Indegree[V]==0){q.push(V);Earlist[V]=0;}}/*开始进行Top Sort*/while(!q.empty()) {front=q.front();q.pop();cnt++;//TopOrder[cnt++]=front;W=Graph->head[front].AdjNode; while(W) {if(Earlist[W->vertexIndex]<Earlist[front] + W->weight) //计算最早完成时间 Earlist[W->vertexIndex]=Earlist[front]+W->weight; if(--Indegree[W->vertexIndex] == 0){q.push(W->vertexIndex);}	W=W->next;	} }if(cnt!=Graph->vertexNumber)return result;else {  // Earlist数组中的最大值就是最早完成时间for(V=0;V<Graph->vertexNumber;V++)  {if(Earlist[V]>result)result=Earlist[V];}return result;} 
}
  1. BuildGraph( ) ：通过邻接表存储图，属于建图的基础练习

3. 完整AC编码

  1. 本文如果对你有帮助，请点赞鼓励 ，谢谢 😊
  2. 如有建议或意见，欢迎留言
#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;typedef int vertex;
typedef int wightType;
#define max 100struct EdgeStruc
{vertex V1;vertex V2;wightType weight;
};
typedef struct EdgeStruc *ptrEdge; typedef struct AdjNodeStructure *ptrAdjNode;
struct AdjNodeStructure
{vertex vertexIndex;wightType weight;ptrAdjNode next;
};struct HeadNode
{ptrAdjNode AdjNode;
};
typedef struct HeadNode HeadNodeArray[max];struct GraphStructure
{int vertexNumber;int edgeNumber;HeadNodeArray head;
};
typedef struct GraphStructure *ptrGraph;ptrGraph Graph;
int Earlist[max]={0}; //统计最早完成时间 
//vertex TopOrder[max]; //存放拓扑排序的结果void CreateNullNodeGraph();
void BuildGraph();
void insertEdge(ptrEdge Edge);
int TopSort();int main()
{	int result;BuildGraph();result=TopSort();if(!result)cout<<"Impossible";elsecout<<result;return 0;
} int TopSort()
{int Indegree[Graph->vertexNumber],cnt=0,front,result=0;vertex V;ptrAdjNode W;queue<vertex> q;/* 初始化入度 */for(V=0;V<Graph->vertexNumber;V++)Indegree[V]=0;/*遍历图 得到Indegree[] */for(V=0;V<Graph->vertexNumber;V++){W=Graph->head[V].AdjNode;while(W){Indegree[W->vertexIndex]++;W=W->next;}		} /*将所有入度为0的顶点入列*/for(V=0;V<Graph->vertexNumber;V++) {if(Indegree[V]==0){q.push(V);Earlist[V]=0;}}/*开始进行Top Sort*/while(!q.empty()) {front=q.front();q.pop();cnt++;//TopOrder[cnt++]=front;W=Graph->head[front].AdjNode; while(W) {if(Earlist[W->vertexIndex]<Earlist[front] + W->weight) //计算最早完成时间 Earlist[W->vertexIndex]=Earlist[front]+W->weight; if(--Indegree[W->vertexIndex] == 0){q.push(W->vertexIndex);}	W=W->next;	} }if(cnt!=Graph->vertexNumber)return result;else {  // Earlist数组中的最大值就是最早完成时间for(V=0;V<Graph->vertexNumber;V++)  {if(Earlist[V]>result)result=Earlist[V];}return result;} 
}void CreateNullNodeGraph()
{Graph=(ptrGraph)malloc(sizeof(struct GraphStructure));cin>>Graph->vertexNumber>>Graph->edgeNumber;for(int i=0;i<Graph->vertexNumber;i++){Graph->head[i].AdjNode=NULL;}
}void BuildGraph()
{ptrEdge Edge;  CreateNullNodeGraph();for(int i=0;i<Graph->edgeNumber;i++){Edge=(ptrEdge)malloc(sizeof(struct EdgeStruc));cin>>Edge->V1>>Edge->V2>>Edge->weight;insertEdge(Edge);	}return;
}void insertEdge(ptrEdge Edge)
{ptrAdjNode N;N=(ptrAdjNode)malloc(sizeof(struct AdjNodeStructure));N->vertexIndex=Edge->V2;N->weight=Edge->weight;N->next=Graph->head[Edge->V1].AdjNode;Graph->head[Edge->V1].AdjNode=N;return;
}

四、参考

  1. 浙江大学 陈越、何钦铭老师主讲的数据结构

这篇关于PTA How Long Does It Take 思路分析及代码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/858841。

相关文章

SpringCloud集成AlloyDB的示例代码

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么？AlloyDB 的工作原理2.搭建测试环境3.代码工程1.
阅读更多...
Java调用Python代码的几种方法小结

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python
阅读更多...
Java中ArrayList的8种浅拷贝方式示例代码

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》：本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝？ArrayList 浅拷贝的重要性方法一：使用构造函数方法二：使用 addAll(
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
SpringBoot使用注解集成Redis缓存的示例代码

SpringBoot使用注解集成Redis缓存的示例代码

《SpringBoot使用注解集成Redis缓存的示例代码》：本文主要介绍在SpringBoot中使用注解集成Redis缓存的步骤,包括添加依赖、创建相关配置类、需要缓存数据的类（Tes... 目录一、创建 Caching 配置类二、创建需要缓存数据的类三、测试方法Spring Boot 熟悉后，集成一个外
阅读更多...
锐捷和腾达哪个好? 两个品牌路由器对比分析

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时，Tenda和锐捷都是备受关注的品牌，各自有独特的产品特点和市场定位，选择哪个品牌的路由器更合适，实际上取决于你的具体需求和使用场景，我们从... 在选购路由器时，锐捷和腾达都是市场上备受关注的品牌，但它们的定位和特点却有所不同。锐捷更偏向企业级和专
阅读更多...
在C#中合并和解析相对路径方式

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C
阅读更多...
轻松掌握python的dataclass让你的代码更简洁优雅

轻松掌握python的dataclass让你的代码更简洁优雅

《轻松掌握python的dataclass让你的代码更简洁优雅》本文总结了几个我在使用Python的dataclass时常用的技巧,dataclass装饰器可以帮助我们简化数据类的定义过程,包括设置默... 目录1. 传统的类定义方式2. dataclass装饰器定义类2.1. 默认值2.2. 隐藏敏感信息
阅读更多...
opencv实现像素统计的示例代码

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2