本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-06 08:54:21
图论
坑：同余最短路
存图
vector,链式前向星（邻接链表）
并查集
启发式合并，路径压缩
带权并查集
种类并查集（扩展域并查集）
把一个点扩为$x,x+n,x+2\times n$三个点表示三个类群，然后判断
转化为前缀和$s_y-s_x = $ 奇/偶
奇偶性相同的是一个集合，不同的是一个集合
然后连边，判冲突
也可用带权并查集
奇偶性相同的连$0$ 边，不同的连$1$ 边
序列并查集
$f_i$ 表示序列中 $i$ 及以后第一个没被染色的点
用并查集维护
将两个属性值连无向边
如果有环，就都能满足
如果是树，除根节点，都能满足
那就选最大的为根
求联通块的 $mex$
（本题也可用二分图匹配）
最小生成树
Kruscal
Prim
可二分
将$<=n$ 的边加入图，看$s,t$是否联通
但是最小生成树显然更优
从小到大加入边，看是否联通
一眼最小生成树
但是两两连边的话显然要炸
显然要去除冗边
分别按$x,y,z$排序
每个点向前后的点连边
跨过其他点连的边显然没用（跟他连边的代价都够把其间的点都联通了）
然后排三次序，跑最小生成树
（重边也没关系，因为最小生成树每次取权值最小的）
思维题
转化为得知$s_i$ (前缀和)的奇偶性
$s_i$ 向 $s_j$ 连边,表示奇偶性相关
$s_0 =0$
目的转化为求$s_0,s_1,s_2......s_n$ 在同一连通块内的最小代价
于是将 $s_{i-1}$ 与 $s_j$ 连边，代价为 $c_{i,j}$
跑最小生成树
结论：严格次小生成树一定是拿非树边换树边
枚举所有非树边，尝试替换环上的边
（记录最大值和次大值，如果等于最大值，那么替换次大值，否则替换最大值）（非树边一定大于等于树边）
最短路
bfs
dijistra
spfa
floyd
原来的边权为$0$，转之后的边权为$1$,跑最短路
(因为每次的坐标x+1，y+1或x+1,y-1...,因此坐标之和奇偶性不变，因此一个格子不会既有左上到右下，又有左下到右上)
小优化：
因为是$0/1$最短路，跑bfs即可，复杂度$O(n+m)$
拓展：
边权为$[0,k]$($k$较小）
开$k$ 个桶，把操作后的扔进相应桶里，从小到大枚举桶，时间复杂度（n+m），空间（$nk+m$）
二分，判最短路
分层图板子
看到除法，二分 $or$ 斜率优化
显然二分
如果二分出来的mid为 $k$，则问题就转化为是否存在一个$\sum F_i/\sum T_i \ge k$
$$ \sum (F_i-k\times T_i)\ge0$$
然后 spfa 判环
设 $f_i$ 表示彻底消灭 $i$ 的最小代价
$$f_i=min(k_i,s_i+f_j)$$
类比 dijistra
同余最短路
同余方程$\to$ 最短路
$f_t=b$ 表示 满足$b mod a_i = t$的最小的 $ b $ ，无论加多少个$a_1$ 都是合法的
$f_0=0$
$f_t \to (f_t+a_i)mod a_1$ 边权$a_i$
跑最短路
$f_t=min(f_{t-a_i}moda_1+a_i)$
差分约束
$a\to b$,边权为 $w$ 表示$b-a\le w$
差分约束板子
差分约束妙用
$$1\le dis_b-dis_a\le9$$
$$dis_a-dis_b \le -1$$
$$dis_b-dis_a\le9$$
跑差分约束
拓扑排序
一眼二分
对$> mid$ 的边拓扑
对于$\le mid$ 的边
肯定是从小拓扑序的点指向大拓扑序的点
然后判断方向是否改变，判断是否可行，统计答案
首先不是字典序最小
怎么办？
保证小的尽量在前面，即保证大的尽量在后面
把较小的放在后面，不如直接把最大的放在后面
我们可以建反图
跑一遍字典序最大的拓扑序，倒序输出，即为答案
基环树
同前面的某一道题
遍历切掉环上的一条边,跑最大独立集
(或随机选环上的一个点,强制选或不选,跑dp)
转化题意,即求基环树(森林)上的直径
不经过环,直接dfs
经过环,求两段的最大值
Tarjan
魔改割点
将夫妻和情人关系区分开连，一个男向女，一个女向男,跑tarjan
二分图
板子
对能攻击到的染与自己不同的颜色，跑最大独立集
将每行看作点，每列看做点，一个黑格子就让行和列连边，跑最大匹配是否为 $n$
网络流
ek
dinic
重点在建图
番外
“奇技淫巧”
“精妙建图”
鲁ICP备2025150228号