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。

相关文章

Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java 虚拟线程的创建与使用深度解析

Java 虚拟线程的创建与使用深度解析

《Java虚拟线程的创建与使用深度解析》虚拟线程是Java19中以预览特性形式引入,Java21起正式发布的轻量级线程,本文给大家介绍Java虚拟线程的创建与使用,感兴趣的朋友一起看看吧... 目录一、虚拟线程简介1.1 什么是虚拟线程？1.2 为什么需要虚拟线程？二、虚拟线程与平台线程对比代码对比示例：三
阅读更多...
Nginx分布式部署流程分析

Nginx分布式部署流程分析

《Nginx分布式部署流程分析》文章介绍Nginx在分布式部署中的反向代理和负载均衡作用,用于分发请求、减轻服务器压力及解决session共享问题,涵盖配置方法、策略及Java项目应用,并提及分布式事... 目录分布式部署NginxJava中的代理代理分为正向代理和反向代理正向代理反向代理Nginx应用场景
阅读更多...
一文解析C#中的StringSplitOptions枚举

一文解析C#中的StringSplitOptions枚举

《一文解析C#中的StringSplitOptions枚举》StringSplitOptions是C#中的一个枚举类型,用于控制string.Split()方法分割字符串时的行为,核心作用是处理分割后... 目录C#的StringSplitOptions枚举1.StringSplitOptions枚举的常用
阅读更多...
Python函数作用域与闭包举例深度解析

Python函数作用域与闭包举例深度解析

《Python函数作用域与闭包举例深度解析》Python函数的作用域规则和闭包是编程中的关键概念,它们决定了变量的访问和生命周期,：本文主要介绍Python函数作用域与闭包的相关资料,文中通过代码... 目录1. 基础作用域访问示例1：访问全局变量示例2：访问外层函数变量2. 闭包基础示例3：简单闭包示例4
阅读更多...
MyBatis延迟加载与多级缓存全解析

MyBatis延迟加载与多级缓存全解析

《MyBatis延迟加载与多级缓存全解析》文章介绍MyBatis的延迟加载与多级缓存机制,延迟加载按需加载关联数据提升性能,一级缓存会话级默认开启,二级缓存工厂级支持跨会话共享,增删改操作会清空对应缓... 目录MyBATis延迟加载策略一对多示例一对多示例MyBatis框架的缓存一级缓存二级缓存MyBat
阅读更多...
Redis中的有序集合zset从使用到原理分析

Redis中的有序集合zset从使用到原理分析

《Redis中的有序集合zset从使用到原理分析》Redis有序集合(zset)是字符串与分值的有序映射,通过跳跃表和哈希表结合实现高效有序性管理,适用于排行榜、延迟队列等场景,其时间复杂度低,内存占... 目录开篇：排行榜背后的秘密一、zset的基本使用1.1 常用命令1.2 Java客户端示例二、zse
阅读更多...
Redis中的AOF原理及分析

Redis中的AOF原理及分析

《Redis中的AOF原理及分析》Redis的AOF通过记录所有写操作命令实现持久化,支持always/everysec/no三种同步策略,重写机制优化文件体积,与RDB结合可平衡数据安全与恢复效率... 目录开篇：从日记本到AOF一、AOF的基本执行流程1. 命令执行与记录2. AOF重写机制二、AOF的
阅读更多...
前端缓存策略的自解方案全解析

前端缓存策略的自解方案全解析

《前端缓存策略的自解方案全解析》缓存从来都是前端的一个痛点,很多前端搞不清楚缓存到底是何物,：本文主要介绍前端缓存的自解方案,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录一、为什么“清缓存”成了技术圈的梗二、先给缓存“把个脉”：浏览器到底缓存了谁？三、设计思路：把“发版”做成“自愈”四、代码
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2