要发财的小熊猫很靠谱 level
获赞
1
粉丝
2
关注
0
看过 TA
53
门头沟学院
2025
C++
IP属地:江西
暂未填写个人简介
私信
关注
2024-12-30 17:16
门头沟学院 C++
Bellman_ford 队列优化算法:Bellman_ford 算法每次松弛 都是对所有边进行松弛。但真正有效的松弛,是基于已经计算过的节点在做的松弛;队列优化算法只对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛,用队列来记录上次松弛的时候更新过的节点。已经在队列里的元素不用重复添加,而从队列里取出的时候,要取消标记。这是因为每个要加入队列的节点,都是一次松弛后得到了更小距离的节点,以它作为出发节点的边也可以获得更小距离。所以如果此时该节点已经再队列里,没有必要再加一次,因为它还没出队更新,一旦出队就会更新好当前情况下的最小距离,但是从队列取出时要取消标记,因为可能该节点的最小距离还会得到更新(找到其它节点到它的路最短),那么以它为出发节点的边也要进行更新!bellman_ford判断负权回路:在有负权回路的情况下,一直都会有更短的最短路,所以松弛第n次,minDist数组也会发生改变所以判断是否有负权回路,就是在松弛n-1次的基础上再多松弛一次,看minDist数组是否发生变化bellman_ford单源有限最短路:计算在最多经过 k 个城市的条件下,从城市 src 到城市 dst 的最低运输成本,最多经过 k 个城市, 那么是 k + 1条边相连的节点,所以本题就是求:起点最多经过k + 1 条边到达终点的最短距离。根据之前对所有边松弛一次,相当于计算 起点到达 与起点一条边相连的节点 的最短距离得知:对所有边松弛 k + 1次,就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。在有负权回路的情况下,还需要注意使用上次的minDist数组
0 点赞 评论 收藏
分享
2024-12-27 14:40
已编辑
门头沟学院 C++
0 点赞 评论 收藏
分享
2024-12-26 22:13
门头沟学院 C++
dijkstra算法求最短路径:与prim算法很相似,步骤几乎一直,但prim求的是所有结点都连通起来的最小值,而dijkstra求的是有向图的起点到终点的最短路径,不需要连通所有结点,所以求结果的过程稍有不同。prim算法中的minDist数组求的是当前结点(还未加入生成树的结点)到现有生成树的最近距离,这个距离会因为每次生成树新节点的加入进行更新),输出结果也是对minDist数组进行累加;而dijkstra算法中minDist数组求的是当前结点到起点(结点1)的最小距离,输出结果就是终点(结点n)到起点的最小距离minDist[n]。//dijkstra三部曲://1、选起点到哪个节点近且该节点未被访问过//2、对该最近节点标记为已访问//3、更新还未访问节点到起点的距离(即更新minDist数组)拓扑排序:给出一个有向图(具有复杂的依赖关系),把这个有向图转成线性的排序就叫拓扑排序,如大学排课,文件处理等。同时要检测有向图中是否有环,有环则不能得到线性排序,所以拓扑排序也是图论中判断有向无环图的常用方法。思路:1、找到入度为0(出发结点)的结点,加入结果集2、将该结点从图中移除3、循环上面两步,直到图中所有结点都被移除用vector记录每个文件的入度,入度为0的结点存放在queue里,依赖关系放在unordered_map>里当构造依赖关系时就将依赖别人的文件入度+1,最后遍历将入度为0的结点加入队列,然后依次将队列里的结点弹出,此时将该节点从图中移除意味着依赖它的结点的入度要-1,并判断是否入度为0,是的话加入队列。判断有 有向环 的存在:如果找不到入度为0的节点了且此时结果集中的元素个数不等于图中结点个数,就说明有环
0 点赞 评论 收藏
分享
2024-12-23 16:57
门头沟学院 C++
并查集功能:1、寻找根节点,函数:find(int u),判断这个节点的祖先节点是哪个2、将两个节点接入到同一个集合,函数:join(int u, int v),将两个节点连在同一个根节点上3、判断两个节点是否在同一个集合,函数:isSame(int u, int v),就是判断两个节点是不是同一个根节点代码模板:int n = 1005; // n根据题目中节点数量而定,一般比节点数量大一点就好vector father = vector (n, 0); // C++里的一种数组结构// 并查集初始化void init() {    for (int i = 0; i         father[i] = i;    }}// 并查集里寻根的过程int find(int u) {    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩}// 判断 u 和 v是否找到同一个根bool isSame(int u, int v) {    u = find(u);    v = find(v);    return u == v;}// 将v->u 这条边加入并查集void join(int u, int v) {    u = find(u); // 寻找u的根    v = find(v); // 寻找v的根    // 如果发现根相同,则说明在一个集合,不用两个节点相连直接返回    if (u == v) return ;     father[v] = u;}今天得开始写毕业论文了,先把框架整理好!最近学了workflow作为客户端和服务端(http服务器和静态资源管理服务器),开始学wfrest包装的workflow作为HTTP服务器,主要是减少了url提取查询参数,方法,路径这些复杂的字符串切割操作,简化了workflow服务端的使用。
0 点赞 评论 收藏
分享
2024-12-14 15:22
门头沟学院 C++
647、回文子串://动态规划解法:布尔类型的二维dp数组        //dp[i][j]:区间范围[i,j](左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。        //递推公式:主要分为s[i]和s[j]相等和不相等的情况        //不相等时:dp[i][j] = false;        //相等时:        //1、i=j时为单个字符,所以dp[i][j] = true        //2、j-i=1时为两个相同的字符,所以dp[i][j] = true        //3、看dp[i][j]是否为true,可以由dp[i+1][j-1]推导出来        //初始化:全初始化为false,后面再去判断更新        //遍历顺序:由于dp[i][j]要由dp[i+1][j-1]推导出来,所有i从大到小,j从小到大遍历(因为是字符串区间,所以j一定要大于i)516、回文子序列://回文子序列不要求连续        //dp[i][j]:区间范围[i,j](左闭右闭)的子串的最长回文子序列        //递推公式:主要看s[i]和s[j]是否相等        //如果相等,则dp[i][j] = dp[i+1][j-1] + 2;//注意单个字符和两个字符的情况        //不相等,则dp[i][j] = max(dp[i+1][j], dp[i][j-1]);        //初始化:全初始化为0;        //遍历顺序i--,j++
0 点赞 评论 收藏
分享
2024-12-14 14:04
门头沟学院 C++
115、不同的子序列://dp[i][j]:以i-1结尾的字符串s中有多少个以j-1结尾的字符串t        //递推公式:删除s中的字符以匹配t。        //两元素相等时,可以考虑在s中使用该元素,或者不使用该元素。        //if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];        //else dp[i][j] = dp[i-1][j];        //初始化:dp[i][0](t为空字符串)初始化为1,dp[0][j](s为空字符串)初始化为0583、两个字符串的删除操作,使得word1与word2相同//两个字符串的删除操作,就相当于找到两个字符串的最长公共子序列        //dp[i][j]:长度[0,i-1]的s1和长度[0,j-1]的s2的最长公共子序列的长度72、编辑距离//要将word1转换为word2难点是当两个元素不相等时,分别取增删替操作中最小的        //dp[i][j]:以i-1结尾的word1转换成以j-1结尾的word2最小编辑次数        //递推公式:主要分为相等和不相等两种情况的操作        //if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];        //else dp[i][j] = min(dp[i-1][j] + 1,//word1删除当前字符        //                    min(dp[i-1][j-1] + 1,//word1替换当前字符        //                    dp[i][j-1] + 1))//word1插入一个字符        //初始化:dp[i][0](word2为空字符,所以要删掉所有word1的元素)初始化为i        //dp[0][j](word1为空字符,所以要插入所有word2的元素)初始化为j
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务