笔记

Johnson 全源最短路算法学习笔记

0 条评论 OI 笔记 无标签 hycqwq
Floyd 算法可以以 $O(n^3)$ 的时间求得图上全源最短路。然而这个复杂度在许多题目中是不可接受的。这时我们可以使用另外一种全源最短路算法 Johnson。Johnson 全源最短路径算法 - OI Wiki引入考虑到全源最短路就相当于对每个节点跑一边单源最短路，我们尝试在 $n$ 次单源最短路的基础上做一些优化。跑 $n$ 次 Dijkstra，总复杂度为 $O(nm \log m...

网络流学习笔记

0 条评论 OI 笔记 无标签 hycqwq
网络流（network flow）就是一个网络（有向图）上的流。网络流简介 - OI Wiki一、前置知识1.1 割（cut）把网络分为 $S, T$ 两部分，使得源点在 $S$ 中，汇点在 $T$ 中，其容量 $V$ 为所有从 $S$ 到 $T$ 的边的容量之和，这就是一个割。1.2 增广路（augmenting path）从源到汇的流（经过的边的流量的最小值）大于 $0$ 的路径。1.3...

函数指针使用笔记

0 条评论 笔记 无标签 hycqwq
在开始之前，我们先复习一下变量指针的内容：指针是一个变量在内存中的地址，一个变量只对应一个指针，但是可能有多个指针指向一个变量所占的内存空间（因为一个变量可能会占好几个字节，但是每个字节都对应一个指针）。但是在我们的印象中，函数是一串代码，不应该是存在内存里的呀。实际上我们的程序在执行的时候也是放在内存里的，所以像函数这样一条条的指令也就有了确切的地址。这样函数也就有了自己的内存地址。至于怎...

auto 类型与 Lambda 表达式使用笔记

0 条评论 笔记 无标签 hycqwq
本文所有内容均仅能在 C++11 及以上标准中使用。一、前置知识1.1 auto 类型auto 的本义是“自己”。auto 类型可以根据赋值，自己推断应该使用什么类型。这其实是为了方便程序猿不用打一些很长的类型。举个栗子，遍历一个 map，如果不用 auto，代码如下。map<class1, class2> m; for (map<class1, class2>::i...