2024年3月

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...