今天复习了一下网络流，复习了之前学习的使用普通SPFA不断找增广路单路增广的算法，并且学习了一下zkw网络流和折中的算法——SPFA多路增广算法，今天就让我们来一起学习一下最小(最大)费用流吧！ 什么是费用流问题 在一般的最大流题目中，一般每条边只有一个参数——容量，但是费用流中每条边还多了一个参数——费用，也就是说在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研...
今天在陈学康学长的指导下，了解并学习了k短路算法，发现也并没有想象中的那么难。那么这篇BLOG，就让我们一起来学习k短路算法吧！ 什么是k短路 我们在之前的学习当中，肯定已经学习过了最短路算法，经典的求解最短路算法有SPFA和Dijkstra之类的，这这里就不再讲解了。今天我们要求解的如果不是最短路，而是第k短路怎么办？比如给你一道题： 给你一副有N个点(N≤1000)，M条边(M≤1...
在之前的BLOG里，我们谈论过了二分图的一部分问题——最大匹配问题，并且一起学习了解决这类问题的匈牙利算法，还没有学过的同学可以 点击我学习最大匹配算法。在这一篇BLOG里，我们将一同学习二分图的另一个问题——最大带权匹配问题。 什么是二分图最大带权匹配 那么什么是二分图的最大带权匹配呢？实现我们都应该知道什么是二分图的最大匹配。不知道也没关系，我们先看一下下面这个问题：比如我们有3个公...
在众多的线段树题目中，有一种题目一直占有一席之地，那就是染色问题，这篇BLOG，我们就针对染色问题，来浅谈一下这一类问题的解决方法 一维染色问题 这一类题目，一般都有一个固定的样式，当你对题目进行简化以后，总会得到类似与下面这种模型类似： 在一条数轴上，依次进行n次操作，每次操作读入3个数,x,y,z，表示在区间[x,y]中涂上颜色z，后涂上的颜色会覆盖之前涂上的颜色。问最后我们还能看...
今天在某神犇老师的带领下学习了后缀自动机，刚开始学的时候还是一脸懵逼的，后面在周围大佬们孜孜不倦的帮助下终于学会了后缀数组。这篇BLOG，就让我们携手走进后缀数组吧。 什么是后缀数组 我们先来一个一个概念搞懂： 子串 若我们有一个长度为n的字符串S，设字符串内的点为[1,n]，那么我们从中任意截取一段[l,r], 若1≤l≤r≤n，那么称 截取出来的这段子字符串SS为原字符串的子串。即若...