大路

最短路

Floyd

多源最短路径

本质上是$dp$

$f[k][i][j]$表示从$i$到$j$只经过编号$1…k$点的最短路,可以解决诸如按顺序加点的问题

需要考虑重边(边权取$min$)、自环(读入边后$w[i][i]=0$)

Dijkstra

单源最短路径

标号设定算法,基于贪心思想,因此只适用于边权非负

两点最短路优化:$T$被标记后直接退出

$O((n+m)\log n)$ 堆优化

Spfa

单源最短路径

标号迭代算法,$Bellman-Ford$算法的队列优化,可以处理负权边

两点最短路优化:$if(d[u]>=d[T])$ $continue;$

$SLF$优化:每次入队后,$if(d[q[head+1]]>d[tail])$ $swap(q[head+1],q[tail]);$

$LLL$优化:每次$v$出队后,$if(d[v]>$队列中所有$d$的平均值) $q[++tail]=v,continue ;$

$O(ke)$,其中$k$是一个与出题人$rp$非线性相关的常数

判负环

使用$dfs$版$spfa$,比较科学

最短路树&图

  • case1:跑完最短路后记录一个点由那个点转移而来,形成一棵树
  • case2:保留图中所有可能成为最短路的边,形成一个图

分层图最短路中,同一层内的顺序可能会与最短路图中的点的拓扑序相关

最短路计数

统计点对间的最短路条数,某条边经过的最短路径数,etc

Floyd可以方便地实现,当然Dijkstra也可以

次短路

枚举在最短路上但不在次短路上的边

k短路

$A*$算法

差分约束系统

传递闭包

大概就是求出所有点对间的联通性

1
2
3
4
bitset<N+5> b[N+5];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(b[i][k]) b[i]|=b[k];

距离

欧几里得距离:两点间的真实距离
曼哈顿距离:各维坐标差绝对值的和;各维度独立,可以分开处理
切比雪夫距离:各维坐标差绝对值的最大值,坐标系旋转$45°$可以和曼哈顿距离互相转化
汉明距离:两个字符串不同的位数

各种距离

路径

欧拉通路

通过图中每条边一次且仅一次的路径

判定

无向联通图:图中只有0个或2个度为奇数的节点

有向联通图:有且仅有两个顶点:其中一个入度数比出度数大1,另一个入度数比出度数小1,其余的顶点入度数等于出度数

欧拉回路

通过图中每条边一次且仅一次并回到起点的路径

判定

无向联通图:图中所有节点度均为偶数

有向联通图:图中所有节点入度等于出度

输出路径

哈密顿回路

从给定的起点到给定的终点经过图中所有点的路径

分享到: