膜拜 zzh 大神。
原链接。
最短路
几种常用的求最短路方式
-
\(Floyd\) \(O(n^{3})\)
\(f[i][j]=min(f[i][j],f[i][k]+f[k][j])\)
\(k\)是最外层循环 \(k\)循环到\(m\)时 \(f[i][j]\)此时就表示只经过编号\(1\sim m\)的点,从\(i\to j\)的最短路还可以倍增求定长步数是否可达
矩阵求 定长路径统计，定长最短路，限长路径计数/最短路等
见oi-wiki -
\(Bellman\)–\(Ford\) O(n*m)
用队列优化的spfa慎用 -
\(Dijkstra\)
重要知识点：最短路树
题目要求出在不经过原来\(1\)节点到\(i\)节点最短路上最后一条边的前提下，\(1\)节点到 \(i\) 节点的最短路
求出最短路径树，由于1到每个点的最短路唯一，最短路径树也唯一
易证：新的路肯定只会经过一条非树边 因为另一条肯定可以被树上一条路径代替
那么答案就很明显了:\(ans_i=min(dis[u]+dis[v]+w_{u,v}-dis[i]))\)
将所有非树边按照答案排一遍序,更新能更新的点，并查集优化即可
题：SDOI2009 Elaxia的路线
JOI2018 Commuter Pass
-
同余最短路
通过同余构造某些状态，状态之间的关系类似于两点之间的带权有向边。
那么可以以此建图，将某些问题转化为最短路问题，再使用具有优秀时间复杂度的算法求解。
最小生成树
-
Kruskal 算法
重点讲Kruskal重构树的性质：
-
性质1
\(u\)到\(v\)的最小瓶颈路的最大边权,等于他们的\(LCA\)的点权 -
性质2
任意一个结点到根的路径上的结点点权递增 -
性质3
从一个结点\(u\)出发,能通过的边的边权阈值为\(c\)。
\(u\)能到达的结点数为，\(u\)的点权小于等于\(c\)最远的祖先的子树大小/2+1
- 次小生成树
枚举非树边\((u,v)\),在树上找到一条最大边替换，更新答案即可
严格再维护次小值即可
题：严格次小生成树
二分图
-
染色法判断二分图
-
扩展域并查集判断二分图
-
匈牙利算法求最大匹配
二分图的一些性质
1.二分图的最小点覆盖\(=\)二分图的最大匹配
2.最大独立集\(=n-\)最大匹配
3.有向无环图的最小路径点覆盖\(=n-\)拆点二分图的最大匹配
拆点二分图：对于一条有向边\((u,v)\)，将\(u\)向\(v+n\)连一条边4.有向无环图的最小路径可重点覆盖
先跑一遍floyd 求出每个点能到的所有点 再跑一遍最小点覆盖即可
连通分量
-
强连通分量
缩点后是一个有向无环图 -
点双连通分量
一个割点至少属于两个点双中 -
边双连通分量
缩点后是一棵树
连通分量的套路就是 缩点后跑\(dp\),难度主要还是在dp上