图论基础术语
- 欧拉回路，哈密尔顿回路，环，简单环
- 强连通块（任意两点互相连通），点双连通分量（任意两点之间至少有两条路径），边双连通分量（任意两边之间至少有两条路径）
- 有向无环图（DAG）
- 默认有(n)个点，(m)条边
DFS森林
- Tree Edge指树边
- Back Edge指连向祖先的边
- Forward Edge指连向子孙的边
- Cross Edge指连向树其他分支的边
- 在无向图中只存在Tree Edge和Back Edge
最短路
SSSP
- 松弛操作（用一边更新两点之间最短路）
- Dijkstra，贪心，无负权边（可优先队列优化）
- Bellman Ford，每个点/边松弛(n-1)次，可以有负权边，所以可以判断负环（可队列优化）
- 时间复杂度为(O(mn))，优化后可达(O((n+m)log_2n))（SPFA容易被卡成(O(nm))，需谨慎使用）
变种
- 边权是0/1
- 双端队列，如果是0从头部插入，否则从尾部插入
- 总长不超过W，正权
- 使用0~w的桶+链表维护这些点，时间复杂度为(O(m+W))
APSP
-
Floyd算法，动态规划（(O(n^3))）
for(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]); } } } -
Johnson算法（负权）（(O(nmlog_2n))）
给每一个点标号标号(h(v))，把每条边((u,v))边权改成(s(u,v)+h(u)-h(v))
对于s-t的一条路径，不会改变最短路
从1号点出发跑一遍最短路，记(h(v)=dis(v))
由不等时可以得到(dis(u)+w(u,v)ge dis(v))，非负，跑Dijkstra
差分约束系统
- 根据最短路有不等式(div(v)le dis(u)+w(u,v))
- 恰好存在一个u使得不等式存在
如何判断存在？
- 对原图求一遍最短路
- 对原图取反，边权取反，求最长路
- 标号对应能取到的最值
- 相同则唯一
最小生成树
-
Prim
-
Kruskal
-
对于当前状态，有(k)个联通块
我们考虑每个连通块连出去的边里最小的一条
也就是考虑(k)条边
排序，贪心选取
新的边合并后，会得到新的(p)个连通块
重复到只剩(1)个连通块
每一次会至少使连通块数量折半
-
复杂度为(O(n^2))或(O(mlog_2m))
最小瓶颈生成树
- 使得生成树最大的边权最小
-
- 二分答案，类似找第(k)大值的方法
- 跑最小生成树
强连通分量
- Tarjan
对于每个点，有dfn与low两个值
dfn表示的是它被访问的顺序
low表示的是，它及他后面所有访问的点里通过非树边能够回顾到之前的点的dfn的最小值
显然对于一个强连通分量，存在一个节点dfn=low
节点即为所求
每次剖出多个环的嵌套
割点与桥
- 考虑dfs树，每条边对应着一个到祖先的路径
- 非树边打标记，如对于((u,v))这条边，在(u)点打上+1的标记，(v)点打上-1的标记
- v到v的父亲的树边的覆盖次数为子树标记和
- 割点同理
双连通分量
- 点连通度：最小的点集使得删去之后图不连通
- 边连通度：最小的边集使得删去之后图不连通
- 如果一个图的点连通度(>1)，那么是点双联通的，边同理
- 双连通分量为图中极大双联通子图
考虑dfs树。每条非树边对应着会祖宗的路径，打上标记
例如边((u,v))，u点+1，v点-1
v到v的父亲的树边覆盖次数为子树内所有标记的和
拓扑排序
每次去掉图中入度为(0)的点，复杂度为(O(n+m))
如果最后不为空集则这个图不为DAG
如果求最小的序列，把队列改成优先队列
二分图
-
可以分成两部分，每部分无环
-
等价于该图没有奇环
-
匈牙利算法：每次找一条增广路
每次试图给一个新的点找到对象
对于前面的每一个人，如果没有配偶就配对
否则我问对面那个女孩子的男友能不能找个别的女孩子
能的话两人都有女朋友了
2-SAT
- 一堆变量的二元限制
- 问是否存在合法的赋值
任何一个强连通分量，所有点必须一个状态
- 缩点
- 拆点
对于一个点x，新建点x'
x代表取，x'代表不取
所以可以连上否定条件
如果x与x'处于同一个强连通分量，就无解
求拓扑，取一点进答案，这个点的对立面不能去，删掉
输出方案
欧拉回路
-
求出一条恰好每条边经过一次
-
充分必要条件
- 是强连通分量
- 出度等于入度
-
圈套圈算法
任选起点，从起点开始dfs，每条边只能走一边，当没有可走时把x压入答案队列，欧拉回路为队列逆序
网络流
Dinic（(O(n^2m))）
在当前图上从(S)跑到(T)
这样每个人都有一个标号，也就是它属于bfs的第几层
每次找到的点，他的bfs编号都必须上一个点+1，强行分层
然后选一条分层的路作为增广路
例题
-
普通快乐的最短路径1
有(n)个点的图，有(m)个关键点
求关键点之间的最短路径
(1le kle nle 2cdot10^5\1le mle10^6)
枚举答案(S)和(T)的不同二进制位，把关键点分成两个集合(A)和(B)
(A)向(B)大力跑最短路径更新答案即可
-
普通快乐的最短路径2
多组询问求两点最短路
(1le nle 10^5\0<m-n<100\1le qle10^5)
先建一棵生成树，对于不在的树上的用BFS向全图跑最短路
对于询问(x,y)，要么就是树上走，要么经过其余点中的某一个，枚举经过哪个，松弛
-
普通快乐的最小生成树
询问那些边一定是在最小生成树上的
(3le nle 500)
跑最小生成树，对于每一条边，边权一样即可替换
-
Boruvka
任意两点连边的费用是(|a_i-a_j|)，求MST
Boruvka只维护最短边
对于每一块，用set维护不在块里的点的权值
然后枚举连通块里的点，比如权值为(x)
即在set中找(x)相邻的点
去掉边之间的关系
-
普通快乐的关键点
对于一张有向图，定义(a)是key point当且仅当所有其他点要不能到它，要不它能到它，求所有的key point
(nle 10^5\mle 10^6)
缩点，对新图跑拓扑
考虑i是key point的等价条件是比它拓扑排序后的点它能到，比它拓扑排序前的点能到它
两个相似，拓扑，取反，再拓扑
所以只需考虑前半部分
我们维护每个点的出边里在拓扑序最靠前的序号是多少
那么判断前面的点能否到i
