在前面的很长一段时间里，我都一直在更新机器学习的内容。现在机器学习的大致内容也已过半，所以我计划利用这段时间，学习复习一些经典算法。这篇BLOG，就让我们一同来看看三种并查集算法吧！ 普通并查集 并查集的概念 什么是并查集呢？并查集，是在一些有 N 个元素的集合应用问题中，体现点归属类别的树状集合。我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集...
在最近的训练中，遇到了很多与LCA有关的算法。今天就让我们一起来重温一下求解LCA的三种主流算法吧！ LCA简介 在求解LCA之前，我们需要先知道什么叫LCA。LCA（Least Common Ancestors），即最近公共祖先，是指在有根树或者DAG中，某两个结点u和v最近的公共祖先。 觉得很迷？没问题，下面我们来通过一个例子来理解一下LCA的内涵，我们首先有一颗可爱的树(特别感谢大...
今天复习了一下网络流，复习了之前学习的使用普通SPFA不断找增广路单路增广的算法，并且学习了一下zkw网络流和折中的算法——SPFA多路增广算法，今天就让我们来一起学习一下最小(最大)费用流吧！ 什么是费用流问题 在一般的最大流题目中，一般每条边只有一个参数——容量，但是费用流中每条边还多了一个参数——费用，也就是说在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研...
今天在陈学康学长的指导下，了解并学习了k短路算法，发现也并没有想象中的那么难。那么这篇BLOG，就让我们一起来学习k短路算法吧！ 什么是k短路 我们在之前的学习当中，肯定已经学习过了最短路算法，经典的求解最短路算法有SPFA和Dijkstra之类的，这这里就不再讲解了。今天我们要求解的如果不是最短路，而是第k短路怎么办？比如给你一道题： 给你一副有N个点(N≤1000)，M条边(M≤1...
在之前的BLOG里，我们谈论过了二分图的一部分问题——最大匹配问题，并且一起学习了解决这类问题的匈牙利算法，还没有学过的同学可以 点击我学习最大匹配算法。在这一篇BLOG里，我们将一同学习二分图的另一个问题——最大带权匹配问题。 什么是二分图最大带权匹配 那么什么是二分图的最大带权匹配呢？实现我们都应该知道什么是二分图的最大匹配。不知道也没关系，我们先看一下下面这个问题：比如我们有3个公...