Aesrium の树洞

基本纯数论，且过程让人觉得十分眼熟

一道可以暴力解决的并查集

一道比较简单的拓扑排序题（虽然需要一点数学证明）

Bellman-Ford 判环

数据坑人但的确很简单的贪心

一种非常简单易懂的图论算法

一种用来求强连通分量的有趣的算法

需要一点思维的贪心

在图论中，有一类算法，是专门拿来算两点之间最短距离的，被称之为最短路算法。 一共有四种最短路算法，分别是：Floyd，Dijkstra，Bellman-Ford 和 SPFA，它们时间复杂度各不相同，同时也具有各自的缺陷，今天就来介绍一下这四种算法。 参考题目：P1744 采购特价商品（四种算法参考代码均为这道题） PS：因为图论刚起步，所以为了熟悉一下，代码都是用的链式前向星存图，其实这四种都有自己的方式，下面会讲到。 Floyed Floyd 和其它三种不一样，是一种全源最短路径算法，也就是说，它能求出任意点为起点，任意点为终点的最短距离，而其它三种只能求出以某一点为起点，任意点为终点的最短距离，即单源最短路径。 Floyd 算法时间复杂度为O(n3)O(n^{3})O(n3)，核心代码如下： 1234for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]) ...

非正解的并查集经典题型