$$\rm 图论$$

$$\large\rm ——~The~Study~Notes~of~CCA's~——$$

$$\rm 欧拉回路$$

$$\rm 定义$$

• 欧拉路径：如果图中的一个路径包括每个边恰好一次，则该路径称为欧拉路径 $(Euler~Path)$ 。

• 欧拉回路：首尾相接的欧拉路径被称为欧拉回路 。

$$\rm 判定$$

$\quad$由于每一条边都要经过恰好一次，因此对于除了起点和终点之外的任意一个节点，只要进来，一定要出去。

• 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图只有一个存在边的连通块。

• 一个无向图存在欧拉路径，当且仅当该图中奇点的数量为 $0$ 或 $2$ 且该图只有一个存在边的连通块。

• 一个有向图存在欧拉回路，当且仅当所有点的入度等于出度。

• 一个混合图存在欧拉回路，当且仅当存在一个对所有无向边定向的方案，使得所有点的入度等于出度。需要用到网络流。

$$\rm 求出$$

$\quad$用 $dfs$ 算法求出一张图的欧拉回路 。

$\quad$给每一条边记一个 $vis$ 数组，表示其是否被访问，然后从一个点出发，遍历所有的边。

$\quad$直接 $dfs$ 的话可能会有一些点无法被遍历到，于是在记录答案的时候可以倒着记录，即当通过 $u\to v$ 这条边的时候，可以先将点 $v$ $dfs$ 完，再加入 $u\to v$ 这条边 。

$$\rm [UOJ117]欧拉回路$$

$Problem$

$\quad$给定一张有向/无向图，输出一条欧拉回路。

$Solution$

$\quad$欧拉回路板子题 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm [CF547D]Mike~and~Fish$$

$Problem$

$\quad$给定平面上一些点，要给每个点黑白染色，要求同一行或同一列上两种颜色的点数之差不大于 $1$ 。

$Solution$

$\quad$离散化后对于每个点的横纵坐标连边，所有度数为奇数的点向 $0$ 连边，对每个连通块跑欧拉回路，然后按照欧拉回路黑白染色 。

$\quad$需要注意的是， $x$ 坐标和 $y$ 坐标的点不能搞混，可以将所有 $y$ 坐标形成的点编号 $+N$ 。

$\quad$时间复杂度 $\mathcal{O}(N+M)$ 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm 拓扑排序$$

$$\rm 定义$$

$\quad$所谓拓扑排序，就是把有向图上的 $n$ 个点重新标号为 $1$ 到 $n$，满足对于任意一条边 $u\to v$，都有 $u < v$ 。

$\quad$并不是所有的图都能进行拓扑排序，只要图中有环，那么就可以导出矛盾。

$\quad$可以进行拓扑排序的图称为有向无环图 $（DAG）$，有很多优美的性质，比如可以在拓扑序上进行 $DP$ 。

$$\rm 求法$$

$\quad$记录一下每一个点的入度和出度，用一个队列维护当前所有入度为 $0$ 的点。

$\quad$每次拿出来一个入度为 $0$ 的点并且将它加到拓扑序中，然后枚举出边更新度数。

$\quad$时间复杂度 $\mathcal{O}(n + m)$。

$\quad$在拓扑排序的过程中可以顺带进行 $DP$ 。

$$\rm 最短路$$

$$\rm Floyd传递闭包$$

$\quad$有时候我们需要维护一些具有传递性的关系，如相等，连通等。

$\quad$初始条件往往是给定几组关系，要把所有的关系求出来。

$\quad$可以把 $Floyd$ 算法做一下调整：

$$dis_{i,j}=min{dis_{i,k}+dis_{k,j}}$$

$$\Longrightarrow dis_{i,j}=dis_{i,j}~|~(dis_{i,k}~\&~dis_{k,j})$$

$$\rm 多源最短路-Johnson重赋权$$

$\quad$对于多源最短路，如果我们枚举一个点然后跑堆优化的 $Dijkstr$a，那么复杂度是 $\mathcal{O}(NMlogN)$ 的，在图比较稀疏的情况下，这个复杂度要优于 $Floyd$ 算法的 $\mathcal{O}(N^{3})$ 。

$\quad$但是 $Dijkstra$ 算法要求所有边权均非负，于是就有了重赋权的技巧。

$\quad$我们新建一个 $0$ 号点，并且从这个点出发向所有点连一条边权为 $0$ 的边，然后跑单源最短路。($SPFA$ 或者 $Bellman-Ford$) 设距离数组为 $h$， 接下来对于每条边 $(u, v)$， 令

$$w^{\prime}(u, v)=w(u, v)+h(u)-h(v)$$

$\quad$这样所有的边权就都变成非负了，我们就可以跑 $Dijkstra$ 算法了。

$\quad$证明：

$\quad$首先由于 $h(v) \leqslant h(u)+w(u, v),$ 新图的边权一定非负。

$\quad$设新图上的最短路径为 $d^{\prime}$，原图上的最短路径为 $d$ 。

$$\begin{aligned}d^{\prime}(u, v)=& \min _{a_{1}, a_{2}, \ldots, a_{k}} w^{\prime}\left(u, a_{1}\right)+w^{\prime}\left(a_{1}, a_{2}\right)+\cdots+w^{\prime}\left(a_{k}, v\right) \\\\=& \min _{a_{1}, a_{2}, \ldots, a_{k}} w\left(u, a_{1}\right)+\left(h(u)-h\left(a_{1}\right)\right)\&+w\left(a_{1}, a_{2}\right)+\left(h\left(a_{2}\right)-h\left(a_{1}\right)\right)+\cdots+w\left(a_{k}, v\right)+\left(h(v)-h\left(a_{k}\right)\right) \\\\=& h(u)-h(v)+\min _{a_{1}, a_{2}, \ldots, a_{k}} w\left(u, a_{1}\right)+\cdots+w\left(a_{k}, v\right) \\\\=& h(u)-h(v)+d(u, v)\end{aligned}$$

$$\rm 最短路图$$

$\quad$所谓最短路树，就是在求完从 $S$ 出发的单源最短路之后，只保留最短路上的边形成的数据结构。

$\quad$只需要在求的过程中维护一个 $pre$ 数组表示这个点的前驱即可。

$\quad$很多最短路的变种都需要用这个算法。

$$\rm [JLOI2011]飞行路线$$

$Solution$

$\quad$分层图最短路板子。

$\quad$记 $dp_{i,j}$ 表示当前已经到达 $i$，使用了 $j$ 次免费机会的最短路。

$\quad$时间复杂度 $\mathcal{O}(K(N+M)\cdot log(KN))$

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm [LGOJ2761]软件补丁问题$$

$Solution$

$\quad$考虑以所有的状态为点，用补丁作为转移，跑一遍 $SPFA$ 。

$\quad$复杂度 $\mathcal{O}(k\cdot 2^n)$ 。

$$\rm [NOIP2017]逛公园$$

$Problem$

$\quad$给定一张 $n$ 个点 $m$ 条边的图，问从 $1$ 到 $n$，与最短路的长度差不超过 $k$ 的路径有多少条。

$\quad$可能有 $0$ 边，如果数量无限输出 $−1$。

$\quad n \leqslant 10^5, m\leqslant 2\times 10^5, k \leqslant 50$ 。

$Solution$

$\quad$令 $dp_{i,j}$ 表示走到 $i$ 号点，已经比最短路长 $j$ 的方案数，枚举 $j$ ，模仿最短路的转移方式（扩散型 $DP$ ）即可 。

$\quad$当图中存在长度为 $0$ 的边时，可能形成长度为 $0$ 的环。这时候判断一下是否存在一条长度与最短路长度之差不大于 $k$ 且经过这个长度为 $0$ 的路径即可，有的话输出 $-1$ 。

$$\rm 最小生成树$$

$$\rm Prim算法$$

$\quad$类比 $Dijkstra$ 算法，维护一个集合 $S$，表示这个集合中的生成树已经确定了。

$\quad$算法流程和 $Dijkstra$ 一样，唯一的区别是用 $w(u, v)$ 去更新 $d_v$，而不是用 $d_u + w(u, v)$。

$\quad$时间复杂度 $O(N^2)$，同样可以用堆优化。

$$\rm Kruskal算法$$

$\quad$因为是求的最小生成树，所以使用贪心的思路，把所有的边权从小到大排序，然后一条一条尝试加入，用并查集维护连通性。

$\quad$可以发现这样一定能得到原图的最小生成树，证明如下：

$\quad$如果某一条边 $(u, v)$ 不属于最小生成树，那么考虑最小生成树上连接 $u, v$ 的路径，这上面一定有一条边权不小于 $w(u, v)$ 的边（因为我们是从小到大枚举的所有边），这样替换后答案一定不会变劣。

$\quad$时间复杂度 $\mathcal{O}(M\cdot logM)$ 。

$$\rm Kruskal重构树$$

$\quad$$Kruskal$ 重构树是基于 $Kruskal$ 最小生成树的一种算法，它主要通过将边权转化成点权实现 。

$\quad$算法流程如下：

$\qquad 1>$ 将所有边按照边权排序，维护 $r_x$ 表示并查集中 $x$ 所在连通块的根节点 。

$\qquad 2>$ 枚举所有的边 $u\to v$ ，若 $u,v$ 不连通，则新建一个结点 $x$，其权值为 $w(u\to v)$，连接 $r_u$ 与 $x$ ，$r_v$ 与 $x$ ，令 $r_u=r_v=x$ 。

$\qquad 3>$ 不断重复上述过程，直到所有的点均连通 。

$\quad$时间复杂度 $\mathcal{O}(M\cdot logM)$ 。

$\quad$经过 $Kruskal$ 重构可以得到一棵有 $2n − 1$ 个节点的二叉树，其中叶节点为原图中的点，其余的点代表原图中的边，并且满足父节点权值大于等于子节点。

$\quad$同时，它还可以做如下事情：

• 求 $u, v$ 之间路径上的最大边权 $\longrightarrow$ 求重构树上 $u,v$ 两个点的 $LCA$ 。

• 只保留边权小于等于 $x$ 的边形成的树$\longrightarrow$ 重构树上点权小于等于 $x$ 的点的子树。

$$\rm Borůvka算法$$

$\quad$一种求最小生成树的算法，虽然比较冷门但是很多题需要用到这个算法。

$\quad$维护当前形成的所有连通块，接下来对于每一个连通块，找到边权最小的出边，然后合并两个连通块。不断重复这个操作，直到整张图变成一个连通块。

$\quad$由于每次操作连通块数量至少减半，所以时间复杂度最坏为 $\mathcal{O}((N + M) log N)$ ，随机图复杂度可以降到 $\mathcal{O}(n + m)$ 。

$$\rm [NOIP2013]货车运输$$

$Problem$

$\quad$给定一张 $n$ 个点， $m$ 条边的图，问从 $u$ 到 $v$ 的所有路径中，最小边权最大是多少。

$\quad n \leqslant 10^4~,~m \leqslant 5 \times 10^4~,~q \leqslant 3 \times 10^4$

$Solution$

$\quad$建立 $Kruskal$ 重构树，树剖求两点 $LCA$ 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm [NOI2018]归程$$

$Solution$

$\quad$先跑一遍最短路，把从一号点开始的所有点的最短路处理出来，作为点权。

$\quad$问题转化成了：求一个点只经过长度 $\leqslant t$ 的边能到达的最小点权 。

$\quad$考虑从海拔大的开始加起，建立 $Kruskal$ 重构树。

$\quad$对重构树上的每个点记录海拔和子树内最小点权，查询的时候倍增即可。

$\quad$时间复杂度 $\mathcal{O}(N\cdot logN)$ 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm Tarjan算法$$

$$\rm 强连通分量$$

$\quad$如果一个点的 $dfs$ 序等于他能访问到的最小的 $dfs$ 序，那么在 $dfs$ 树中，它的下方会出现一个强连通分量，且所有最小能访问到的 $dfs$ 序等于它的属于这个强连通分量 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm 割点/割边（桥）$$

$\quad$如果在 $dfs$ 树上，某个结点 $u$ 存在一个子节点 $v$ ，满足 $low_v\geqslant dfn_u$ ，则说明 $v$ 想到达 $u$ 的祖先结点必须经过 $u$，则 $u$ 是一个割点 。

$\quad$当然，根节点不能通过这种方式来判断，应该看它的子节点数是否大于等于 $2$，如果是，则它为割点 。

$\quad$遍历的时候要记得判掉父子边 。

$\quad$和判断割点的方法几乎一模一样，唯一的区别是判断 $dfn_u<low_v$ 而不是 $dfn_u\leqslant low_v$ 。（如果从 $v$ 出发连 $u$ 都无法到达，那么 $(u, v)$ 就是一条桥边）。

$\quad$判断割边的时候根节点不需要特殊考虑 。

$$\rm [NOIP2009]最优贸易$$

$Solution$

$\quad$$Tarjan$ 缩点后对每个强连通分量记录一个最小值和一个最大值，在 $DAG$ 上 $DP$ 求可以到达每个点的最小值即可。

$$\rm [HNOI2012]矿场搭建$$

$Solution$

$\quad$假设图是连通的。

$\quad$首先求一遍点双连通分量，并且找出所有的割点。

$\quad$如果坍塌的不是割点，由于整张图还是连通的，所以只需要在这个点之外有一个出口即可。

$\quad$如果坍塌的是割点，则要求去掉这个割点之后每一个连通块内至少有一个出口。

$\quad$可以发现，如果一个点双连通分量里只有一个割点，那么这个双连通分量中必须要设置一个不同于割点的出口。

$\quad$特判一下整张图双连通的情况，这种情况下随便找两个点弄两个出口即可。

$\quad$方案数乘一下就可以了。

$$\rm [POJ3352]Road~Construction$$

$Problem$

$\quad$给定一张图，求至少添加多少条边可以使整张图边双连通。

$Solution$

$\quad$首先求一遍边双连通分量，然后缩点。

$\quad$可以发现缩完点之后一定是一棵树。

$\quad$将叶子两两相连即可。如果有 $k$ 个叶子，答案即为 $\left\lceil\frac{k}{2}\right\rceil$ 。

$\quad$要注意特判一下 $k = 1$ 的情况。

$$二分图匹配$$

$$相关定义$$

• 匹配：在图论中，一个匹配 $(matching)$ 是一个边的集合，其中任意两条边都没有公共顶点。

• 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

• 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

$\quad$如果要求一般图的最大匹配，需要用 $\mathcal{O}(N^3)$ 的带花树，至少是 $NOI+$ 的算法。在联赛阶段，一般只关注二分图的匹配问题。

• 二分图：如果一个图的顶点能够被分为两个集合 $X, Y$，满足每一个集合内部都没有边相连，那么这张图被称作是一张二分图。

$$最大匹配—匈牙利算法$$

$\quad$首先做两个比较重要的定义：

• 交替路：从一个未匹配点出发，依次经过非匹配边——匹配边——非匹配边—— $……$ 形成的路径叫交替路。

• 增广路：从一个未匹配点出发，依次经过非匹配边——匹配边——非匹配边—— $……$ ——非匹配边，最后到达一个未匹配点 形成的路径叫增广路。

$\quad$注意到，一旦我们找出了一条增广路，将这条路径上所有匹配边和非匹配边取反，就可以让匹配数量 $+1$ 。

$\quad$匈牙利算法就是基于这个原理。

$\quad$假设已经得到了一个匹配，希望找一个更大的匹配 。

$\quad$从一个未匹配的点开始出发进行 $dfs$ ，如果找出了一条增广路，就代表増广成功，找到了一个更大的匹配 。

$\quad$如果増广失败，可以证明此时就是最大匹配 。

$\quad$由于每个点只会被増广一次，所以时间复杂度为 $\mathcal{O}(N\cdot (N+M))$ 。

$$最小点覆盖$$

$\quad$选取最少的点，使得每条边的两端都至少有一个点被选中。

$\quad$二分图的最小点覆盖 $=$ 最大匹配 。

$\quad Proof:$

• 由于最大匹配中的所有边都必须要被覆盖，所以匹配中的每一个点对都至少有一个点被选中 。

• 选中这些点后，如果还有边没有被覆盖，则找到一条增广路，矛盾。

$$最大独立集$$

$\quad$选取最多的点，使得任意两个点不相邻。

$\quad$最大独立集 $=$ 点数 $-$ 最小点覆盖 $=$ 点数 $-$ 最大匹配 。

$\quad Proof:$

• 由于最小点覆盖覆盖了所有边，因此选取剩余的点一定是一个合法的独立集。

• 若存在更大的独立集，则取补集后得到了一个更小的点覆盖，矛盾。

$$最小边覆盖$$

$\quad$选取最少的边，使得每一个点都被覆盖 。

$\quad$最小边覆盖 $=$ 点数 $-$ 最大匹配 。

$\quad Proof：$

• 先选取所有的匹配边，然后对剩下的每一个点都选择一条和它相连的边，可以得到一个边覆盖。

• 若存在更小的边覆盖，则因为连通块数量 $=$ 点数 $-$ 边数，这个边覆盖在原图上形成了更多的连通块，每一个连通块内选一条边，就得到了一个更大的匹配。

$$\rm [ZJOI2007]矩阵游戏$$

$Problem$

$\quad$给定一个 $n \times n$ 的黑白方阵，可以任意交换两行或者两列。

$\quad$求是否能够让主对角线上都是黑色。

$\quad 1\leqslant n \leqslant 200$，多测最多 $20$ 组 。

$Solution$

$\quad$建立一张二分图，左边是行，右边是列。若 $(i,j)$ 为黑色，则将左边的 $i$ 与右边的 $j$ 连边 。

$\quad$能通过交换使得主对角线上都是黑色当且仅当此二分图存在完美匹配 。

$Code$

$\quad \longrightarrow~$$\color{Black}{Link}$

$$\rm [POJ2446]Chessboard$$

$Problem$

$\quad$一个 $n \times m$ 的网格，其中有若干个位置被删掉了。

$\quad$现在需要用 $1 \times 2$ 的骨牌覆盖其余所有的位置，判断是否可行。

$\quad 1 \leqslant n, m \leqslant 32$

$Solution$

$\quad$考虑给矩阵黑白染色，使用每张骨牌一定会覆盖一个白点和一个黑点。

$\quad$对黑点和白点分别建点，给相邻的格子连边，判断是否有二分图完美匹配 。

$$\rm [ZOJ3988]Prime~Set$$

$\quad$首先筛质数，暴力处理出所有能组成质数的数对。

$\quad$在忽略 $1+1=2$ 的情况下，所有合法的数对一定奇偶不同。

$\quad$于是考虑建图，跑二分图最大匹配，然后把 $1+1=2$ 的情况考虑进去，剩下的贪心选取 。

$$\rm [POJ2226]Muddy~Fields$$

$Problem$

$\quad$一个 $n \times m$ 的矩阵，其中有一些格子上有泥。

$\quad$需要用木板覆盖所有有泥的格子。木板的宽度是 $1$ ，长度任意。

$\quad$木板不能盖到没有泥的格子，木板之间可以重叠。

$\quad$求最少用多少块木板。

$\quad 1 \leqslant n, m \leqslant 50$

$Solution$

$\quad$木板肯定尽量长，所以只需要起始位置和方向，这块木板就确定了。

$\quad$对于一个有泥的格子 $(i, j)$，它被覆盖等价于经过它的横竖方向的木板至少存在其中一个。

$\quad$建图，则问题变成了求二分图的最小点覆盖。