图论刷题日记

写在前面

关于图论，大概包括这些

图的存储
DFS（图论）
BFS（图论）
树上问题
矩阵树定理
有向无环图
拓扑排序
最小生成树
斯坦纳树
最小树形图
最小直径生成树
最短路
拆点
差分约束
k 短路
同余最短路
连通性相关
2-SAT
欧拉图
哈密顿图
二分图
最小环
平面图
图的着色
网络流
Prufer 序列
LGV 引理
弦图

次小生成树（非严格，kruscal板）

通过这个图我们可以看到的是，我们需要在原有的最小生成树的基础上，在另外找一个边，使其变成次小生成树

首先我们可以跑一边 (kruscal) 将最小生成树建立出来，并设置一个 (big[i][j]) 表示 (i) 到 (j) 的路径上的最大权值，我们可以通过没有在最小生成树上的边来与最小生成树上的边进行比较，可以得出公式

[ans=min(ans,sml_{tree}+w-big_{i,j} ]

其中 (sml_{tree}) 为最小生成树树的总权值，(w) 为当前不在最小生成树上的边

本笔记主要是记录自己的刷题的历程以及中心思路，对知识点的讲解会不时更新

当图中存在唯一的最小生成树时改算法适用，否则求出来的值不变，仅仅为另外一个次小生成树

模板代码

(spfa)的(dfs)优化+判负环

(spfa) 的 (dfs) 优化通过以一个点为开头，通过松弛操作不断迭代，直到找到找到一个曾经被找过的点时，即可找到一个环

(spfa) 的 (dfs) 优化可以通过二分和公式推论（找松弛条件）来达到求最值的问题，解决了查找时无法准确记录权值的问题

对于找负环，可以有两种做法，一是通过 (dfs) 优化来判断是否有负环，二是可以通过一个点入队的次数(ge n) 来判断

相对于 (dfs) 优化找负环，判断入队次数更加的稳定，且不容易被刻意的样例卡掉

带优化的判入队次数(spfa)判负环模板

(spfa)的(dfs)优化二分模板

(spfa)的(dfs)优化判负环模板

例题

1、黑暗城堡

思路

对于点的数据范围 (nle 10^3),考虑用邻接矩阵进行解答，更加简单
该题首先给出所有的道路修建的可能性边，求解 $ m $ 条边全部建完时 ((1,i)) 的最短路 (D_i)，和实际情况下建好的边所形成的图中 ((1,i)) 的最短路 (S_i) 相等的建设方案数，并对 (2^{31}-1)取摸即可
需要注意的是最好开 (long long)
首先在存图的时候做一个操作，因为是双向图，所有正反存这个没有问题，其次就是可能会出现重复的边的情况，那么对于完全建好的图的最短路，重复的边中不是最小边的所有边没有贡献，所有建边的时候对边的权值取一个 (min) 即可
其次通过邻接矩阵版的(dj)求出从所有的 ((1,i))的最短路
最后根据乘法原理判断就可以了，乘法技术原理可以参考组合数学第一节OVO。