文章目录负环spfa找负环方法一方法二实际效果负环环内路径上的权值和为负。spfa找负环两种基本的方法统计每一个点的入队次数，如果一个点入队了n次，则说明存在负环统计当前每个点中的最短路中所包含的边数，如果当前某个点的最短路所包含的边数大于等于n，也说明存在负环实际上两种方法是等价的，都是判断是否路径包含n条边，nnn条边的话就有n+1n+1n+1个点用的更多的还是第二种方法。方法一cnt[x]:表示x的入队次数cnt[x]:表示x的入队次数cnt[x]:表示x的入队次数#include#defineintlonglong#definerep(i,a,b)for(inti=(a);i(b);+
文章目录前言01背包问题完全背包问题多重背包问题分组背包问题前言背包问题：给我们i件物品，每件物品都有体积vi和权重wi，给我们限制条件，让我们选择在背包的容量内，物品达到权重最大01背包问题01背包问题描述：每件物品只可以使用一次我们看一下题目长什么样：#includeusingnamespacestd;constintN=1010;intv[N],w[N];intf[N][N];//f(i,j)表示体积j的情况下，前i件物品的最大价值intmain(){intn,m;cin>>n>>m;for(inti=1;in;i++)scanf("%d%d",&v[i],&w[i]);for(inti
文章目录前言Part1：朴素Dijkstra算法一、Dijkstra求最短路I1.问题描述输入格式输出格式数据范围输入样例：输出样例：2.算法Part2：堆优化Dijkstra算法一、Dijkstra求最短路II1.题目描述输入格式输出格式数据范围输入样例：输出样例：2.算法Part3：Bellman-Ford算法一、有边数限制的最短路1.题目描述输入格式输出格式数据范围输入样例：输出样例：2.算法Part4：SPFA算法一、spfa求最短路1.题目描述输入格式输出格式数据范围输入样例：输出样例：2.算法二、spfa判断负环1.题目描述输入格式输出格式数据范围输入样例：输出样例：2.算法Par
1.背景介绍图论(GraphTheory)是一门研究有限数量的点(vertex)和线(edge)组成的图(graph)的数学结构和相关问题的学科。图论起源于19世纪的数学家，但是直到20世纪60年代，图论开始被广泛应用于计算机科学、人工智能、操作研究等领域。图论已经成为解决实际问题的强大工具，它在各个领域中发挥着重要作用，例如社交网络、物流、电子商务、金融、通信、计算机网络等。本文将从以下六个方面进行阐述：背景介绍核心概念与联系核心算法原理和具体操作步骤以及数学模型公式详细讲解具体代码实例和详细解释说明未来发展趋势与挑战附录常见问题与解答1.1背景介绍图论起源于19世纪的数学家，但是直到20世
作者推荐动态规划的时间复杂度优化本文涉及知识点数学深度优先搜索图论欧拉环路LeetCode753.破解保险箱有一个需要密码才能打开的保险箱。密码是n位数,密码的每一位都是范围[0,k-1]中的一个数字。保险箱有一种特殊的密码校验方法，你可以随意输入密码序列，保险箱会自动记住最后n位输入，如果匹配，则能够打开保险箱。例如，正确的密码是“345”，并且你输入的是“012345”：输入0之后，最后3位输入是“0”，不正确。输入1之后，最后3位输入是“01”，不正确。输入2之后，最后3位输入是“012”，不正确。输入3之后，最后3位输入是“123”，不正确。输入4之后，最后3位输入是“234”，不正确
作者推荐【动态规划】【前缀和】【C++算法】LCP57.打地鼠本文涉及知识点动态规划汇总LeetCoce1301.最大得分的路径数目给你一个正方形字符数组board，你从数组最右下方的字符‘S’出发。你的目标是到达数组最左上角的字符‘E’，数组剩余的部分为数字字符1,2,…,9或者障碍‘X’。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。一条路径的「得分」定义为：路径上所有数字的和。请你返回一个列表，包含两个整数：第一个整数是「得分」的最大值，第二个整数是得到最大得分的方案数，请把结果对10^9+7取余。如果没有任何路径可以到达终点，请返回[0,0]。示例
【算法-图论基础】最短路径-弗洛伊德算法在生活中，我们往往会遇到这样的问题，从地点A到地点B，选择什么线路，选用哪几种交通工具的组合，花费的时间最少？这个问题中，我们可以借助欧拉使用的数学工具——图论来研究，我们将每一个地点抽象为点，道路或者一个阶段的过程抽象为边，花费的时间就是边的权值。这样，问题就简化为在一个图中找两点之间的最短路径。怎样解决这个问题呢，罗伯特·弗洛伊德给出了答案。弗洛伊德算法采用动态规划的思想，假设我们要找的最短路径在点A与点B之间，那么，图中的所有点只有两种情况，要么在这条最短路径上（也就是中间点），要么不在这条最短路径上，我们可以根据这个来得出状态转移方程，依次将图中
简介本文为自己做的一部分图论题目，作为题单列出，持续更新。题单由题目链接和题解两部分组成，题解部分提供简洁题意，代码仓库：Kaiser-Yang/OJProblems。对于同一个一级标题下的题目，题目难度尽可能做到递增。搜索/BFS/DFSLuoguP3547[POI2013]CEN-PriceList题目链接：LuoguP3547[POI2013]CEN-PriceList题解：LuoguP3547[POI2013]CEN-PriceList题解BFS广度优先搜索最小生成树/Kruskal/Prim/Kruskal重构树/最小瓶颈树LibreOJ136.最小瓶颈路题目链接：LibreOJ13
图神经网络实战——图论0.前言1.图属性1.1有向图和无向图1.2加权图与非加权图1.3连通图非连通图1.4其它图类型2.图概念2.1基本对象2.2图的度量指标2.2邻接矩阵表示法3.图算法3.1广度优先搜索3.2深度优先搜索小结系列链接0.前言图论(Graphtheory)是数学的一个基本分支，涉及对图研究。图是复杂数据结构的可视化表示，有助于理解不同实体之间的关系。图论提供了大量建模和分析现实问题的工具，如交通系统、社交网络和互联网等。在本节中，将介绍图论的基本原理，主要涉及三个方面：图属性、图概念和图算法。首先，我们将定义图及其组成部分；然后，我们将介绍不同类型的图，并分析它们的属性和应
文章目录七、回溯算法八、贪心算法九、动态规划9.1背包问题9.201背包9.3完全背包9.4多重背包十、图论10.1深度优先搜索10.2广度优先搜索10.3并查集 最近博主学习了算法与数据结构的一些视频，在这个文章做一些笔记和心得，本篇文章就写了一些基础算法和数据结构的知识点，具体题目解析会放在另外一篇文章。在学习时已经有C，C++的基础。文章附上了学习的代码，仅供大家参考。如果有问题，有错误欢迎大家留言。算法与数据结构一共有三篇文章，剩余文章可以在【CSDN文章】晚安66博客文章索引找到。七、回溯算法 回溯算法也可以叫回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，有递归就有回溯，因
