1、简易单源最短路
https://www.acwing.com/activity/content/code/content/9526669/
https://www.acwing.com/activity/content/code/content/9526708/
https://www.acwing.com/activity/content/code/content/9527892/
dijkstra跑最长路
这里其实只需要改变是否需要更新dist[j]的条件和改变堆的类型即可
https://www.acwing.com/activity/content/code/content/9527985/
https://www.acwing.com/activity/content/code/content/9528098/
https://www.acwing.com/activity/content/code/content/9528297/
2、单源最短路综合
https://www.acwing.com/activity/content/code/content/9528471/
https://www.acwing.com/activity/content/code/content/9529576/
spfa的优化
(1)SLF优化
SLF优化
这里的方法是把较小元素提前
因为先用较小元素更新后面的值, 所以后面的值被更新的次数会变少
这样就可以降低spfa的常数
这里把较小元素提前当然不能用堆优化, 因为这样会又有一个log
我们可以用双端队列, 虽然不能保证单调, 但是有一定的优化效果
如果新入队的元素比队首元素还要小，就加入到队首，否则排到队尾。
(2)topsort + dijkstra解决有负权的 DAG
DP与最短路
最短路的更新最短路径(dist[j])时相当于DP的状态转移
但是DP只能在DAG上做, 所以可以用最短路来实现
另外dijkstra是无法解决没有累加性质的问题的, 这一点在题目中详细的说了
https://www.acwing.com/activity/content/code/content/9530487/
单源最短路的扩展
求固定终点的最短路(第二种方法更灵活)
2种做法, 第1种是建反图跑dijkstra, 这种做法通俗易懂
第二种做法是新建1个点, 这个点向所有起点连一条长度为0的边
因为这样保证了第1步只在所有的起点上, 并且由于边权是0所以不影响答案
https://www.acwing.com/activity/content/code/content/9530642/
bfs和dijkstra系列满足拓扑序, spfa系列不满足(为什么会在下面中)
https://www.acwing.com/activity/content/code/content/9530987/
https://www.acwing.com/activity/content/code/content/9531181/
https://www.acwing.com/activity/content/code/content/9531291/
4、Floyd
https://www.acwing.com/activity/content/code/content/9531725/
传递闭包：已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通(oi-wiki)
这种问题可以用floyd解决, 思想任然是枚举中转点k, 具体见代码
for (int k = 0; k < n; k ++ )
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
d[i][j] |= d[i][k] && d[k][j];
https://www.acwing.com/activity/content/code/content/9531843/
求最小环问题
我们以环上编号最大的一个点划分状态
任何一个合法的都可以表示成这样
而i->k, j->k只能是固定的w[i, k]和w[k, j]否则无法构成一个环
剩下的i->j就是dist[i, j]
那这样的最短距离就是w[i, k] + w[k, j] + dist[i, j]
最后对于所有的方案取Min, 就是答案
https://www.acwing.com/activity/content/code/content/9532734/
https://www.acwing.com/activity/content/code/content/9532949/
(严格来说不是floyd)
5、最小生成树典型
https://www.acwing.com/activity/content/code/content/9534219/
https://www.acwing.com/activity/content/code/content/9534251/
kruskal的性质：最后一次加进去的边就是最长的一条边
https://www.acwing.com/activity/content/code/content/9534414/
kruskal不做完也是正确的(比如已经有了一些固定边再做kruskal也是对的)
https://www.acwing.com/activity/content/code/content/9534491/
https://www.acwing.com/activity/content/code/content/9534571/
6、最小生成树扩展
https://www.acwing.com/activity/content/code/content/9536143/
https://www.acwing.com/activity/content/code/content/9536203/
经典应用：扩充完全图(题目见下面链接)
完全图的定义：如果任意两个顶点之间都有边的话，该图就称为完全图。
我们先把每个点看做大小是1的联通块, 这个联通快就可以看成完全图
做kruskal算法，当枚举到两个联通块a, b, 我们需要把他们联通块中的每个顶点相连
一共有size[a] * size[b] - 1条边, -1是因为原来a, b之间就有1条边
而边权至少为w[i] + 1, 要不然不能保证新图的最小生成树还是原来那颗
怎么想到kruskal：因为我们要对联通块做最小生成树
https://www.acwing.com/activity/content/code/content/9536441/
次小生成树
做法1：先求最小生成树，然后枚举最小生成树里的边删掉，再求一遍最小生成树
因为最小生成树和次小生成树至少有1条边不一样，然后显然这种做法求得是不严格次小生成树
做法2：先求最小生成树，然后依次枚举非树边，加到最小生成树，同时从原最小生成树中删掉一条边，使得原图任然是一棵树
即求min{sum + w - dist[a][b]}, 其中w > dist[a][b];
就是证明一定存在一个次小生成树和最小生成树只差了一条边
如果差了不止一条边我们其实用最小生成树里的一条边替代更优，所以是对的
并且这种方法能求出严格次小生成树，并且效率更高
https://www.acwing.com/activity/content/code/content/9537089/
7、负环
怎么求负环基础课已经说过了，但是速度是O(nm), 比较慢，这里说一个玄学优化
就是当spfa的效率较慢时，根据经验来说就是存在负环，具体就是所有点的入队次数到达2n左右(或是经验值)就认为有负环(最后一题的优化)
https://www.acwing.com/activity/content/code/content/9537296/
01规划问题：在图论中求一堆的和 / 一堆东西的和最大就是01规划问题
做题套路
1、先二分
2、整理不等式
3、重新定义点权和边权
4、然后就是做一遍比如找负环、dijkstra、kruskal这样的问题
https://www.acwing.com/activity/content/code/content/9537399/
其实spfa找负环的玄学优化不止上面一个
我们可以把队列换成栈，显然栈先进后出的特性能更快找出环，并且这样做绝对是对的
https://www.acwing.com/activity/content/code/content/9537559/
8、差分约束
解决形如xi <= xj + ck的不等式组中所有的x的可行解(ck已知)
我们发现他和最短路的三角不等式很像：如果有(i, j, w)dist[j] < dist[i] + w
那我们发现如果他说xi <= xj + ck, 我们就可以连从j到i的边然后做最短路
最终的dist数组就是答案，无解就是出现负环
注意源点：从源点开始走必须要走到每一条边
(其实对偶一下就是求最长路)
求最大值或最小值
结论：求最小值用最长路，求最大值用最短路
第一先想一下怎么解决x[i] <= c这样的不等式
答案是建超级源点0向i连长度为c的边即可(相当于x[i] <= x[0] + c, 而x[0] = 0)
好，现在我们回到怎么证明这个结论
以求x[i]的最大值为例子
x[i] <= x[j] + c[j]
<= x[k] + c[k] + c[j]
<= x[0] + c[1] + c[2] + ... + c[j]
而x[i]的最大值是所有上界的最小、
而最小的x[0] + c[1] + c[2] + … + c[j]就是求0 -> i的最短路
最小值也可以用这的思考方式得到用最长路
https://www.acwing.com/activity/content/code/content/9537985/
https://www.acwing.com/activity/content/code/content/9539139/
https://www.acwing.com/activity/content/code/content/9539234/
https://www.acwing.com/activity/content/code/content/9539492/
9、最近公共祖先(LCA)
fa数组用递推求 f[i, j] = f[f[i, j - 1], j - 1]
跳法：我们从大到小枚举k,如果跳2^k步没有达到要求,就利用fa数组跳2^k步,是二进制拆分的思想,也叫倍增
为什么跳到儿子：如果不跳到儿子就无法确定跳到的点是不是最近的公共祖先
log要下取整：比如我们需要4 * 10^4, log一下下去整15即可，因为15能跳2^16 - 1
k从大到小枚举：如果不这样做，假设x和y跳2^0跳到同一深度，然后再跳2^1点就相同了，但是此时x或y并不是lca的儿子
https://www.acwing.com/activity/content/code/content/9539852/
tarjan离线求LCA
离线做法：每次询问直接输出答案，不需要再求
在线做法：每次询问都求1遍
把所有点分成3类
0表示没有访问
1表示正在访问
2表示已经访问并回溯
我们发现当我们处理到x时是可以回答2号区域和x相关的询问
因为二号区域每个节点所在子树的根节点就是x和这个子树中的一个点的lca
那我们就可以把每个子树有并查集处理一下，代表元素就是lca
https://www.acwing.com/activity/content/code/content/9540850/
lca求次小生成树O(n log n)
lca求次小生成树和前面的题思想是一样的，只是用lca优化dfs部分
我们除了维护lca的fa数组，再维护d1[i, j]和d2[i, j], 表示从i开始跳2^j步的最大值和次大值
那这个东西我们可以在bfs的过程中去找方法类似于fa分段去找
int anc = f[i][j - 1];
int distance[4] = {d1[i][j - 1], d2[i][j - 1], d1[anc][j - 1], d2[anc][j - 1]};
然后遍历distance数组去找最大值和次大值
然后再lca跳的过程中，用数组把每一段的d1, d2存起来
最后再比较一下得到a, b路径的次大值和最大值，这样就完成了之前dfs的任务
https://www.acwing.com/activity/content/code/content/9541586/
树上差分
给x到y的每个节点上加c的快速做法
d[x] += c, d[y] += c, d[lca] -= c * 2;
然后每条边的长度对应他下面的节点为根的子树和，很明显这样是对的
10、有向图的强联通分量
对于一个有向图,联通分量:对于分量中的任意2点u, v必然可以从u走到v,且从v走到u
强联通分量:极大的联通分量
有向图 -> 缩点(把所有强联通分量分别看成一个点) -> DAG
tarjan求强联通分量
有点难说，看模板理解
配合缩点(变成了DAG)
for (int i = 1; i <= n; i ++ )
for (j, j是i的临点)
if (id[i] != id[j])
add(id[i], id[j]);
并且这里其实按照scc编号递减的顺序排序得到的就是topsort
因为还有一种dfs求topsort的方式
void dfs(int u)
{
for (j, 有一条u -> j的边)
{
dfs(j);
res[cnt ++ ] = u;
}
}
这样明显res是topsort的逆序，而我们发现tarjan的算法过程和他相似
https://www.acwing.com/activity/content/code/content/9542065/
涉及到重要结论
https://www.acwing.com/activity/content/code/content/9542212/
https://www.acwing.com/activity/content/code/content/9542517/
https://www.acwing.com/activity/content/code/content/9542549/
11、无向图的双连通分量
桥：对于一个连通图，如果删掉其中一条边能使图不联通，那么这条边就是桥
边双连通分量e-dcc：极大的不包含桥的联通块
割点：对于一个连通图，如果删掉其中一个点能使图不联通，那么这个点就是割点
点双联通分量v-dcc, 极大的不包含割点的联通块
如何找桥：如果存在dfn(fa) < low(x), 那么x到fa就是一个桥，因为x不能通过回边到fa的fa后再到fa
如何找边双：删掉所有的桥，剩下的每一个都是一个边双
第二种简便的是用stack, 搜到一个就放到栈中，如果dfn[x] == low[x], 说明从x出发走不到上面
说明x到他的父节点就是一个桥，那x所在的子树就是一个边双
技巧：编号为i的边，反边是(i ^ 1)
另外无向图求tarjan只需要判次边是否是反边，不需要in_stk数组
因为in_stk数组是为了看这个点能不能和另一个点组成强联通分量(就是被返祖边和横叉边影响)
而我们仔细想一下：无向图没有横叉边，返祖边无影响(读者自行思考)
涉及重要理论
https://www.acwing.com/activity/content/code/content/9542712/
如何求割点：对于x -> y, 如果low[y] >= dfn[x], 那么如果x不是根节点就是割点
如果x是根节点，那他至少有2个子节点要满足这样的条件
注意下面的题目不是标准求割点，标准的看模板
https://www.acwing.com/activity/content/code/content/9543502/
如何求点双联通分量(伪代码)
孤立点也是点双
if (dfn[x] <= low[y])
{
cnt ++ ;
if (x != root || cnt > 1) x是割点;
将栈中元素直到弹出y为止;
且显然x也属于次点双
}
怎么缩点
1、每个割点单独作为1个点
2、每个点双向他所在点双中整张图的割点连边
https://www.acwing.com/activity/content/code/content/9544788/
12、二分图
(1)二分图 = 不存在奇数环 = 染色法没有矛盾，这里显然，可以用反证法证明充分性和必要性
