NOI 一轮复习 IV：图论

本文是 NOI 一轮复习的第四篇，包括各类图论算法。

图的相关概念

一张图 $G$ 由点集 $V$ 和边集 $E$ 构成。我们用 $d(v)$ 代表节点 $v$ 的度数，如果 $d(v)=|V|-1$，则称 $v$ 为支配点。如果每个点的度数都是 $k$，则该图为 $k-$正则图。

子图

对一张图 $G = (V, E)$，若存在另一张图 $H = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$，则称 $H$ 是 $G$ 的子图，记作 $H \subseteq G$。

若对 $H \subseteq G$，满足 $\forall u, v \in V'$，只要 $(u, v) \in E$，均有 $(u, v) \in E'$，则称 $H$ 是 $G$ 的导出子图。点集为 $V'(V' \subseteq V)$ 的导出子图称为 $V'$ 导出的子图，记作 $G \left[ V' \right]$。

若 $H \subseteq G$ 满足 $V' = V$，则称 $H$ 为 $G$ 的生成子图/支撑子图。

如果一张无向图 $G$ 的某个生成子图 $F$ 为 $k-$正则图，则称 $F$ 为 $G$ 的一个 $k-$因子。

如果有向图 $G = (V, E)$ 的导出子图 $H = G \left[ V^\ast \right]$ 满足 $\forall v \in V^\ast, (v, u) \in E$，有 $u \in V^\ast$，则称 $H$ 为 $G$ 的一个闭合子图。也就是说，图内部是闭合的，不存在一个点在导出子图内，可以通过原图的一条边连到一个不在导出子图内的点。

特殊的图

对于无向简单图，所有本来在图上的边都不在，本来不在的都在，那么这个图就是原无向图的补图。

对于有向图，每条边的方向取反，得到的图就是原图的反图。

特殊集合

一些特殊的点和边的集合有着特殊的意义，这里我们介绍一些常见的。

支配集

对于无向图，如果一个点集的点可以连接到原图的所有点，那么这个点集为原图的支配集。

最小支配集是 NPH 的，我们通常使用 $O(2^n)$ 的枚举算法来求解支配集。

独立集

就是任意两点不相邻的点集。对于树和二分图我们有高效做法，但是一般图上，这个问题是 NPH 的。

匹配

对于图 $G=(V,E)$，若 $E'\in E$ 且 $E'$ 中任意两条边都没有公共端点，且 $E'$ 中没有自环，那么 $E'$ 是 $G$ 的一个匹配，也称为边独立集。如果一个点被匹配的边连接了，那么它就是被匹配的，否则就是不被匹配的。

边数最多的称为最大匹配，如果边带权，那么权重之和最大的匹配称为图的最大权匹配。

如果一个匹配在加入任何一条边后都不再是一个匹配，那么这个匹配就是极大匹配，最大匹配一定是极大匹配。

如果所有点都被匹配了，那么这个匹配是完美匹配。如果在一个匹配中只有一个点不被匹配，那么该匹配为准完美匹配。

对于一个匹配 $M$，若一条路径以非匹配点为起点，每相邻两条边中的一条在匹配中而另一条不在匹配中，那么这条路径称为交替路径；一条非匹配点终止的交替路径称为增广路径。

点覆盖

如果所有边都至少有一个端点在这个点集中，那么这个点集被称为点覆盖集。

点覆盖集一定是支配集，但是极小点覆盖集不一定是极小支配集（考虑一个三元环）。

点覆盖集拥有以下性质：

• 一个点集是点覆盖的充要条件是其补集是独立集。
• 一张图的任何一个匹配的大小都不超过其任何一个点覆盖的大小。

边覆盖

当前边集满足任何一个点都至少是其中一条边的一个端点，那么这个边集称为边覆盖集。

如果知道了最大匹配，那么将所有非匹配点都连一条边加入最大匹配，那么就得到了一个最小边覆盖。同理，如果知道了最小边覆盖，那么将有公共点的边删去到只剩一条就得到了最大匹配。

团

一个图的子点集 $V'$ 中任意两个不同的顶点都相邻，则称 $V'$ 是图 $G$ 的一个团。团对应的导出子图是完全图。说白了最大团就是最大完全子图。

求解一个图的最大团是 NPH 的，可以使用最大团搜索算法（在暴力枚举的基础上加一个不可能成为答案的最优性剪枝）来解决规模较小的图的问题。

Erdős–Gallai 定理

令 $S=(d_1,\cdots,d_n)$ 代表简单无向图的度数，而且 $d$ 为非递增序列，则无向图存在当且仅当 $\sum d$ 是偶数，而且 $\forall k, \text{i.e.}$：

$$\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$$

二分出可能的度数，然后 Erdős–Gallai 定理不难在预处理前缀后做到 $O(n)$ check。代码。

拓扑排序

对于一个有向无环图（DAG）$G$，将 $G$ 中所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$ ，若它们之间存在一条有向边 $(u,v)$，则 $u$ 在线性序列中出现在 $v$ 之前。

如果要让越小的 $i$ 尽可能地出现地早，那么就是让最大的尽可能晚地出现，那么要求反图上字典序最大的拓扑序，也就是菜肴制作。

欧拉路问题

• 欧拉回路：通过图中的每条边恰好一次的回路；
• 欧拉通路：通过图中的每条边恰好一次的通路；
• 欧拉图：有欧拉回路；
• 半欧拉图：有欧拉通路但是没有欧拉回路。

对于无向连通图，如果所有点的度数均为偶数，那么是欧拉图；如果有恰好两个奇度数点，那么是半欧拉图。

而对于一张有向图（显然，它至少需要弱连通），是欧拉图当且仅当其是一个强连通图且每个节点的入度和出度相等。如果这张图恰存在一个顶点的出度比入度小 $1$，另一个点出度比入度大 $1$（这个点为起点），这个图存在欧拉通路。

求解欧拉路可以使用 Hierholzer 算法。采用 DFS 不断找环，遍历当前节点 $u$ 的所有出边，如果没有走过那就遍历，遍历完所有出边后将 $u$ 加入欧拉路径，最后如果遍历的点的个数为 $m+1$，那么就得到了反着的欧拉路径，否则欧拉路径不存在。

在找欧拉回路时，可以从任意节点出发。否则，需要从根据性质找到的点出发。代码。

哈密顿路问题

将欧拉路边的相关定义换成点就成了哈密顿路。通过图中所有顶点一次且仅一次的通路称为哈密顿通路。通过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图。具有哈密顿通路而不具有哈密顿回路的图称为半哈密顿图。

不同于欧拉路，哈密顿路问题不存在多项式复杂度算法。人们尝试过许多方法，包括尝试转化成欧拉路，拆点限制只经过一次然后转化为网络流等，但很可惜都是假做法。

不过网络流的这个做法真的很有启发性，有些特殊条件的图真的可以使用它来求解。

Ore 定理。对于一个简单无向图，如果任意两个不相邻点度数和大于等于 $n$，那么这个图存在哈密顿回路，大于等于 $n-1$ 时存在哈密顿通路。这是一个充分不必要条件。

例题

一些基础题。

[CF1765H] Hospital Queue

Portal.

对于每个点考虑 $n\sim 1$ 能否不成为它的答案，为什么这么干？因为这样处理每个人的 deadline 比较方便。代码。

[CF1152E] Neko and Flashback

Portal.

对于一个 $i$，有 $b_i=\min\{a_i,a_{i+1}\},c_i=\max\{a_i,a_{i+1}\}$，也就是说 $b_i,c_i$ 各是 $a_i,a_{i+1}$ 其中的一个（当然需要 $b_i\le c_i$，否则无解）。 注意这个输出方式，$p$ 的作用是将 $a$ 排列，也就是说我们只需要求出 $a$ 有哪些数组成即可。将给定的 $a_i,a_{i+1}$ 的关系看成一条无向边，走过这个路径就相当于满足了一个限制条件。那么在图上找出欧拉路，就可以得到一个满足所有的限制条件的序列 $a$（需要先离散化后再建图）。时间复杂度 $O((n+m)\log m)$。代码。

[CF36E] Two Paths

Portal.

一道值得一想不值得一写的欧拉路。

原图中最多只能有两个连通块，有两个时就是分别找欧拉路，下面来看只有一个。

如果它只有零个或两个奇点，那么有一个欧拉路，我们把这条路径分开一条边作为一部分，这样就是两部分了（分不出来就无解）！
如果有四个奇点，那么是两个（半）欧拉图拼起来的，因此考虑给两个奇点连一条假边，跑欧拉路，输出的时候以这条假边为分界输出两部分。

由于要输出边的编号，因此用链式前向星方便一些，搞点的时候遍历所有的边寻找对应的是哪一条。代码。

[CF527E] Data Center Drama

Portal.

最终要满足的条件是欧拉图的充要条件，然后定向一下边即可。所以将总度数为奇数的点两两相连，然后不满足加一个自环即可。代码。

* [CF1458D] Flip and Reverse

Portal.

令 $0$ 为 $-1$，$1$ 为 $+1$，然后连 $s_i\rightarrow s_{i+1}$ 的边，那么选择的字符串就是一个环，将字符串取反相当于将一个环的方向反过来。这样，任何一条欧拉回路都可以被构造出来，也就是要求经过的边的字典序最小的欧拉路径，如果回路存在则直接贪心即可。代码。

[ByteDance 2022 Final] Card Shark

Portal.

按照顺序构建，最后要求的是边字典序最小的欧拉路径。代码。

连通性问题

对于一张无向图，如果能够从 $u$ 走到 $v$，那么称 $u$ 和 $v$ 是连通的。一个极大连通子图被称为连通分量。

对于一张有向图，将边替换成无向边可以连通则是弱连通的，不需要替换则是强连通的。同样可以定义连通分量的概念。

大部分的连通性问题都离不开 Tarjan 算法，因此我们先来回顾一下它的工作原理。它对每个结点 $u$ 维护了以下值：

• 时间戳 $dfn_u$；
• 追溯值 $low_u$ 代表 $u$ 的子树中能够回溯到的最早的已经在栈中的结点。

在一个 SCC 中只有一个点满足 $dfn_u=low_u$，该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点。

根据此我们可以求出无向图的点双边双，有向图的 SCC。

无向图的双连通性

如果将 $E'$ 从 $E$ 中删去，$G$ 便不再连通，那么 $E'$ 是 $G$ 的一个边割集，大小为 $1$ 的边割集称为割边/桥。割边一定是树边，判定条件是 $dfn_u<low_v$。

如果 $G$ 不存在大小为 $k-1$ 的边割集，则称 $G$ 是 $k-$边连通的，$k$ 最大时，称 $k$ 为 $G$ 的边连通度。

对于点也可以做同样的定义。割点的判定条件是 $dfn_u\le low_v$，除了 Tarjan 的根节点，根节点需要有两个点满足这个条件；而有多少个点满足这个条件，就是割掉这个点之后图会分成多少个连通块。

门杰定理推论：

• 对于边双内的任意两点 $u,v$，存在经过 $u,v$ 的回路。
• 对于 $\ge 3$ 的点双中的两点 $x,y$（可以相等）与一条边 $e$，存在 $x\rightarrow e \rightarrow y$ 的简单路径；这可以说明存在经过 $x,y$ 必定存在简单环，从 $x$ 可以绕回自己。

仙人掌

如果一个图的所有环都没有相交的边，那么这个图被称为仙人掌。

一般我们使用圆方树来处理仙人掌，这个“代表点”称为“方点”，而原图中的所有点对应“圆点”。代码如下：

广义圆方树

广义圆方树可以高效处理无向图双连通的相关问题。它是 v-DCC 缩点之后的产物。我们建出 v-DCC 的“代表点”并向 v-DCC 内部所有点连边，这样会形成一个菊花图。

也就是说，广义圆方树会将非环边也建一个方点。那么圆方树对应一棵唯一仙人掌的性质便不再成立。因此不推荐处理仙人掌时采用广义圆方树的处理方法。

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    for (int y : G[x]) 
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) { // 找到了一个以 x 为根的 v-DCC
                int z; ++n; // 新建一个方点
                do addedge(z = st[tot--], n); while (z != y); 
                addedge(x, n);
            }
        } 
        else low[x] = min(low[x], dfn[y]);
}

广义圆方树有很美妙的性质，首先是 v-DCC 的引理：

引理：如果 $x$ 与 $y,z$ 均点双连通，但是 $y,z$ 不点双连通，那么 $x$ 是 $y,z$ 的必经点。

然后是广义圆方树的性质：

性质 1：圆点 $x$ 的度数为它所在的 v-DCC 个数。
性质 2：圆方树上只有圆点和方点之间有边。
性质 3：原图上直接相连的 $x,y$ 属于一个 v-DCC，而且如果这个 v-DCC 的大小为 $2$，那么 $(x,y)$ 是割边。值得注意的是，广义圆方树无法处理重边的情况，使用此性质判断割边时需要看一下 $(x,y)$ 边是否为重边。

下面三个是用来做题的：

有向图的强连通性

两点互相可达称为强连通，同样可以使用 Tarjan 算法求解。

void tarjan(int x) {
    dfn[x] = low[x] = ++num; ins[st[++tot] = x] = true;
    for (int y : G[x])
        if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    if (low[x] == dfn[x]) {
        int y; ++cnt;
        do ins[y = st[tot--]] = false, c[y] = cnt; while (x != y); 
    }
}

求解出来的 SCC 编号从大到小就是拓扑序的顺序，可以在缩点后不进行拓扑排序，直接 DP 求解。

2-SAT 问题

k-SAT 问题是指一个变量有 $k$ 种取值，有一些形如 $x_i$ 为 $a$ 或 $x_j$ 为 $b$ 的条件，要求你给出一组合法解。

对于 2-SAT 我们有高效做法。每个变量建立两个点代表其真假，连边之后求出 SCC，同一 SCC 内的变量值相等。

例题

我不知道啊！

[CF51F] Caterpillar

Portal.

毛毛虫上不能长出来环，所以把每一个 e-DCC 缩点，图会变成一个森林，我们需要处理每一棵树，然后把这些树合并，需要树的个数减去一的代价。

由于环必须要合并，如果要直接统计操作次数还需要统计环的大小，不妨换一个思路，默认所有点都需要合并，然后减去不需要合并的。

现在考虑最后一个问题，一棵树怎么处理？直觉告诉我们：这条路径 $p$ 应该是长度为 $d$ 直径，这样才能让要动的点更少。直径可以让我们少合并 $d$ 个点，叶子上的点也可以不用合并（画个图看看），但是直径两端还有两个叶子，所以要减去。代码。

[GDCPC2023] Canvas

Portal.

由于第二次染色是无意义操作，因此考虑逆时旅人，这样变成了只有第一次会影响。

所有的 $x=y=2$ 操作优先执行，所有的 $x=y=1$ 最后执行，然后考虑剩下的填在中间。每有一个 $x+y=3$ 执行就意味着有一个数被定死为 $1$，那么 $(l,1,r,2)$ 相当于“用 $l$ 变成 $1$ 的代价换来 $r$ 变成 $2$”，这个关系可以用有向边 $l\rightarrow r$ 刻画，发现图上的一条链只有链首是 $1$。

SCC 缩点之后只有入度为 $0$ 的点涂一个 $1$ 即可。代码。

[北京省选集训 2019] 完美塔防

Portal.

由于光路是可逆的，因此一个路只能被两个防御塔打到。不难发现这就是一个 2-SAT，处理出打它的炮塔即可。代码。

[CF1835D] Doctor’s Brown Hypothesis

Portal.

$x,y$ 双向可达说明其在同一个 SCC 内，那么 SCC 缩点后分别求答案。

设 $d$

* 「SWTR-8」地地铁铁

Portal.

首先建出圆方树，如果 $x,y$ 间有某个有 $1$ 边的点双，那么它们一定能通过这条路径。

那么对于原图上一条 $0$ 边 $(u,v)$，它恰属于一个点双 $S$ 的方点打标记，统计圆方树上不经过标记点的圆点间路径数即可。这样能计数只经过 $0$ 边的无序对。

看到这里感觉可以容斥了，也就是说要计数只有 0/1 路径，同时有 0 路径和 1 路径。

后者怎么做？可以发现这样的 $(x,y)$ 点对一定在一个点双内。然后在这个点双内恰好满足只有这两个点即被 1 边连，又被 2 边连。代码。

最短路问题

对于无权图（01 带权），可以使用 BFS 求解最短路。

对于多源最短路，可以使用 Floyd 算法，也就是通过 $n$ 轮 DP 来求解最短路。

对于单源最短路，可以使用 Dijkstra 和 SPFA。Dijkstra 基于贪心的思想，每次寻找当前最短的路来走，正确性基于边权非负；SPFA 则通过 $O(nm)$ 的迭代来更新最短路，进而可以判断负环的存在性。

Johnson 通过将边改造为 $(u,v,w+d_u-d_v)$ 来实现，边权是三角形不等式来满足 $\ge 0$，建立超级源点跑 SPFA 即可。代码。

如果我们要求的是最短简单路径（有负环），那么它是一个 NPC 问题。

差分约束

根据三角形不等式进行连边，然后用 SPFA 判断负环。

值得注意的是，如果使用 SPFA 求最短路，那么得到的是字典序最大的解。对于字典序最小的解，只需要将约束条件统统变为 $x_i-x_j\ge y$，然后跑最长路，有正环时无解（就是边的方向和权值都取反）。

[省选联考 2021 A 卷] 矩阵游戏。答案的构造是容易的，然后需要调整这个答案，让每一行和列依次 $+1,-1$，然后错开，直接差分约束即可。代码。

斯坦纳树

如果给定 $n$ 个点，试求连接此 $n$ 个点，总长最短的直线段连接系统，并且并且任意两点都可以通过系统中的直线段组成的折线连接起来，此问题被称为斯坦纳树问题。遗憾的是，这是一个 NPH 问题。

并不是直接将 $S$ 连接起来就是最小的，可能需要借助剩下的 $n-k$ 个点。这种问题可以使用状压 DP 来解决：

设 $f(i,S)$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小边权值和。有转移：$f(i,S)\leftarrow\min\{f(i,T)+f(i,S-T)\},f(i,S)\leftarrow\min\{f(j,S)+w(i,j)\}$。前者可以使用子集 DP 实现，后者可以跑一个最短路（由于图很难特殊构造而且规模很小，所以实际上更建议 SPFA）。代码。

Peach Blossom Spring，注意并不要求完全联通，最后子集和并一下即可。

平面图最小割

如果图 $G$ 能画在平面 $S$ 上，即除顶点处外无边相交，则称 $G$ 可平面嵌入 $S$，$G$ 为可平面图或平面图。画出的没有边相交的图称为 $G$ 的平面表示或平面嵌入。

平面图可以转为对偶图，对偶图的最短路等于原平面图的最小割。给 $G$ 的每个面搞一个点，两个面的公共边可以确定一条与其方向垂直的边。给源点和汇点连线可以将原图分成两个部分，跑最短路即可。

注意左侧和下侧，上侧和右侧分别是同一个点，从右上到左下的最短路即为左上到右下的最小割。模板，代码。

同余最短路

模板。这是一个最短路的变式问题。可以用于求解在某个范围内有多少重量可以由若干物品的完全背包凑出，就是多少数值可以由一些给定的数 $b_i$ 由 $\sum a_i b_i(a_i\ge 0)$ 得到。

我们可以发现，如果 $x$ 可以被表示出，那么 $x+ka_i(k>0)$ 就可以被表示出。因此我们找一个最小的 $a_1$，然后连 $j\rightarrow (j+a_i)\bmod a_1$ 的长度为 $a_i$ 的边，然后我们从 $0$ 开始跑最短路。由于这里图的形态不太能特殊构造，因此使用 SPFA 往往会跑的更快。最后求出的 $f_i$ 代表最小的能被凑出的数，满足 $f_i\bmod a_1 =i$。代码。

答案的求解十分容易。$[0,r]$ 的答案数量为：

$$\sum_{i=0}^{a_1-1}\max\left\{0,\left\lfloor\frac{r-f_i}{a_1}\right\rfloor+1\right\}$$

但为什么要使用最短路呢？实际上这东西是体积模 $m$ 意义下的完全背包，如果重复经过一个点，那么可以选择 $\frac{m}{\gcd(v_i,m)}-1$ 个这类物品。也就是说，会在大小为 $m$ 的环上形成 $\gcd(v_i,m)$ 个子环。

那么在每个子环上转两圈即可统计到所有转移，时间复杂度 $O(nm)$。代码。

如果我们将密度最大的物品选做基准物品，那么其它物品的选择可以替换为若干基准物品，这样可以最大化贡献。设基准物品体积为 $w$，贡献为 $m$。

设 $f_i$ 代表最大的贡献，满足 $V\bmod m=i$。最终权值为 $f_i+\frac{V-V'}{m}w$，因此要最大化 $V-\frac{V'}{m}$，因此贡献应该是 $f_p+c_i-\frac{p+v_i}{m}w$。

可以发现每个 $f_i$ 对应的物品个数一定是不超过 $v$ 的，因此这一部分总容积不超过 $v^2\le V$，不存在误判成有解的情况。代码。

删边最短路

求出 $1,n$ 的最短路树 $T_1,T_n$。如果改的边不是最短路上的边的答案是好算的，否则，我们要算出强制不经过一条边的新的最短路。

我们可以证明，一定可以枚举一条边 $(u,v)$，然后 $1\rightarrow u,v\rightarrow n$ 走的都是最短路。

我们需要保证 $T_1,T_n$ 上 $1\sim n$ 的最短路是相同的一条，否则无法计算。

求出 $p1_i$ 代表 $T_1(1\rightarrow i)$ 与更新路径的最后一个交点（在最短路树上跳，第一个到的最短路上的点，就是 $i$ 与 $n$ 的 LCA），$pn_i$ 同理。

这样维护先修改再单点查询的区间 ckmin 即可。代码。

显然，这种做法并不能在有向图上成立，因为不在最短路上的边可能不止一条。但是，走的路径依然满足中间只有一段不在最短路上的路径。

对于随机有向图可以采用这样一种方式处理：按照顺序遍历原最短路上的边，然后在起点上跑 SPFA，开个堆维护从哪里开始剩下的都走最短路。

k 短路

先建出一棵以 $t$ 为根的最短路树 $T$，$x$ 到 $t$ 的最短路径为 $d_x$。设 $s\rightarrow t$ 的路径上不在 $T$ 中的当前选择的路径的边集为 $P'$，$s\rightarrow t$ 上的所有边为 $P$，那么满足：

1. 将一条边 $e$ 的代价定义为 $\Delta e = w-(d_u-d_v)$，那么 $L_{P'} = d_s + \sum_{e\in P'} \Delta e$；
2. 将 $P$ 和 $P'$ 中所有边按照 $s\rightarrow t$ 经过的顺序依次排列，那么对于 $P'$ 中相邻的边 $e_1,e_2$，那么 $v_{e_1}=u_{e_2}$ 或者 $u_{e_2}$ 是 $v_{e_1}$ 在 $T$ 上的祖先。
3. 对于每一个合法的 $P'$，有且仅有一个 $P$ 与之对应。因为可以根据 $P'$ 还原在 $T$ 上选择了什么。

也就是说，我们现在要求满足性质 $2$ 的第 $k$ 小 $L_p$。

我们记录最后一条边和当前 $L_p$ 的值即可表示 $P'$。初始我们将 $1$ 所有在 $T$ 上的祖先的所有的边中 $\Delta e$ 最小的一条边加入小根堆，然后扩展时只有两种选择：

1. 删掉 $P'$ 结尾的那条边，换成第二大的边；
2. 从 $P'$ 的结尾开始到 $T$ 的路径上，选择最小的边加入。

已知我们开始的描述路径的方式是不漏的，而且我们相当于枚举了所有的待替换边是否进行替换，因此这么做是正确的。

时间复杂度 $O(m\log m+k\log k)$，模板，代码。

$k$ 短路问题能够高效解决，得益于我们只需要一个点即可描述能够被替换的边，如果要输出 $k$ 短路的方案，那么就只能做到 $O(k(n+m)\log m+k\log k)$ 了。

例题

从基础题目到一些复杂的变化。

[THUSCH2017] 巧克力

Portal.

如果颜色数比较少的话直接用斯坦纳树做，但是颜色数很多，钦定的可能也很多。

$k$ 很小，因此考虑将所有颜色随机映射到 $[0,k)$，然后求最小斯坦纳树即可求出最小的巧克力个数 $w$。这 $k$ 个点被分配到不同的颜色时答案合法，正确概率是 $k!/k^k$。随机化做 $200$ 次即可。

然后二分出中位数，将小于等于二分值的权值都设为 $inf-1$，大于的都设为 $inf+1$，然后最小斯坦纳树要 $\le w\times inf$（$inf$ 设置为一个不会影响斯坦纳树选择的巧克力数的一个数即可）。代码。

生成树问题

可以使用以下方法求解：

• Kruskal：基于贪心的思想，按照边权从小到大排序；
• Prim：基于贪心的思想，每次找到不在最小生成树集合，维护 $d_i$ 代表与当前树种权值最小边的权值。

对于次小生成树，其与与最小生成树最多仅有一条边的差距，枚举不是 MST 上的边，考虑删去树上的一条最小边，然后树上倍增找最大值即可。

DFS 或者 BFS 也能构建一棵生成树。对于有些题，我们会根据条件构建一棵生成树（或者是随便一棵生成树），然后再去进行操作。

一些性质

在一张图的所有 MST 上，一个权值的边的数量是一定的。

如果这个询问的每一条边分别都能出现在 MST 上，那么这个询问就是合法的。

离线，按照边权进行排序。对于一条权值为 $w$ 的边，它能被计入 MST，当且仅当所有 $<w$ 的边都被计入 MST 后加入它不会造出一个环来。代码。

Kruskal 重构树

合并两个点集时，我们新建一个节点，权值为边权，得到的二叉树是基于边权的 Kruskal 重构树。

按照点权排序，遍历每个节点 $u$ 和其能到达的节点 $v$，若 $v$ 已经遍历，那么 $w_u\ge w_v$，将 $v$ 的父亲设置为 $u$（如果不在一个集合内），所形成的多叉树是基于边权的 Kruskal 重构树。

重构树满足以下性质：

• 父亲节点的点权大于等于儿子的点权。
• 原图两点路径的瓶颈路等于树上的瓶颈路，即 LCA 处的权值。

Boruvka 算法

对于一个点 $i$，其最小权值的临边必定在 MST 上。那么迭代 $\log n$ 次，每次扫描每条边，然后合并连通块。

考虑一个一个点权地合并，在 Trie 树上启发式合并，去找合并两个连通块地最小边权即可。

可以一开始将点权排序，这样连续的下标在 Trie 上是连续的。

最小度限制生成树

恰好连接，而且看起来就是凸的，因此直接 wqs 二分即可。

我们能做得更好！我们可以求出所有 $f_x(i)-f_x(i-1)$ 并从小到大排序，取出前若干个即可得到答案。

实现上只需要先求出任意一棵生成树，然后贪心调整即可。代码。

最小直径生成树

我们先介绍图的绝对中心。无向图的绝对中心位于图的边上或者节点上，满足该中心到所有点的最短距离的最大值最小。此时对应的最短距离最大值叫做直径。

那么使用 Floyd 算法，绝对中心在点上是好计算的，对于在边 $(u,v,w)$ 上的情况，到点 $i$ 的距离为 $\min\{d_{u,i}+x,d_{v,i}+w-x\}$：

因此我们对于一条边 $(u,v,w)$，按照纵坐标枚举 $i$，然后如果最上面那个东西会产生交点的话，就更新最上面那个东西就可以了，此时用 $\dfrac{d_{u,i}+x+d_{v,p}+(w-x)}{2}$ 更新答案。代码。

对于最小直径生成树，求出图的绝对中心之后，由于图的绝对中心到最远点的距离最小，因此其所对应的半径就是最小直径生成树的半径，因此求出最短路树即可（注意初始距离），代码，注意边界点的特判。

k 小生成树

模板，仿照 $k$ 短路的思路，我们来完成这个问题。

首先求出最小生成树。

对最小生成树求出权值增加量最小的非树边，则有两种选择：强制选择这条边，和强制不选择这条边。对于前者，给出了一棵新的生成树；对于后者，没有给出新的生成树，但边的状态改变了。

如果强制不选择这条边，那么接下来就是决策权值增加量次小的边是否强制选择，依次类推。于是最小生成树给出了若干棵新的生成树，其中第 $i$ 棵生成树钦定了权值增加量前 $i$ 小的非树边不选择，且第 $i$ 小的非树边强制选择。将所有生成树加入优先队列，不断从优先队列取出权值最小的生成树 $k$ 次做上述扩展即可。

注意已经钦定状态的边不可被改变。一条边有四种状态：树边且可被替换，非树边且可加入生成树，树边且不可被替换，非树边且不可加入生成树。在枚举所有非树边时需要跳过所有不可加入生成树的非树边，求一条非树边能替换掉哪条树边时不能替换不可被替换的树边。

如果将每棵生成树抽象为一个点，用一棵有根树描述整个扩展过程（根节点是最小生成树），那么每个非叶子结点有两个儿子，一个是实点，从当前点向下走到实点表示用一条非树边替换了一条树边得到新的生成树，替换出来的那条边变成了非树边且可加入生成树，替换进去的变成了树边不可替换；另一个则是虚点，从当前点向下走到虚点表示当前生成树的一条非树边从可加入变成了不可加入。

这种方式按照顺序枚举了所有的生成树（每条边都枚举了选还是不选），而且按照顺序扩展了次小生成树，因此这么做是对的。

为了避免直接扩展了 $O(m)$ 个虚儿子，应该在取出实点之后再加入兄弟虚点。时间复杂度 $O(km\log m+k\log k)$，运气好是能过的，代码。

例题

都比较经典。

[APIO2008] 免费道路

Portal.

其中有些鹅卵石路是必须的，我们考虑先将必须选择的鹅卵石路选掉，然后将 $k$ 填满，最后再选水泥路即可。代码。

* [CF1583H] Omkar and Tours

Portal.

第一问比较经典，离线，将询问按照 $v$ 从大到小排序，依次加入边，DFS 合并连通块，维护最大值即可。

第二问，希望路径上 $t$ 的最大值尽可能大，Kruskal 重构树！建立一棵基于 $t$ 的边权重构树。设能到达的节点是 $y$，那么答案为 $\max\{a_{\operatorname{LCA}(x,y)}\}$。

由于 LCA 必定在 $x$ 到根节点的路径上，也就是说，我们希望该 LCA 的深度尽可能小。什么时候满足呢？将所有 $y$ 按照 DFS 序排序，其中 DFS 序最小和最大的可能称为答案（Kruskal 重构树是一棵二叉树，想要 LCA 离 $x$ 越远，那么 $y$ 就必定离 $x$ 越远，也就是 DFS 序差越大）。

实现上只需要先建出 Kruskal 重构树，然后在第一问时并查集维护 DFS 序最大最小值。时间复杂度在 $O(n\log n)$ 级别。代码。

* [IOI2018] Werewolf

Portal.

是针对点权限制的 Kruskal 重构树。建立一个 $L$ 来代表子树中都比它小，$R$ 来代表子树中都比它大。将 $s$ 在 $R$ 上倍增到 $a\ge l$ 的最小 $a$，将 $e$ 在 $L$ 上倍增到 $b\le r$ 的最大 $b$，然后就是询问这两个子树有没有公共的子节点，就是二维数点问题。代码。

** [CF1556H] DIY Tree

Portal.

给生成树定义估价函数 $f(T)=\sum_{i=1}^K \max\{0,D_i-d_i\}$，其中 $D_i$ 代表实际度数。

先求出最小生成树，然后对其进行调整。每次选择一条边权最大的，删去后 $f$ 会减小的边 $e_1$，替换成加上后 $f$ 不会变大的边权最小的边 $e_2$，时间复杂度为 $O(n^3)$。

随机化这个过程，我们给 $e_1$ 和 $e_2$ 的选择加上一个概率，不选就接着扫。代码。

[ARC098D] Donation

Portal.

首先，在某点打卡后必不会再次访问某点。

因为若两次访问某点，第一次不打卡，第二次打卡要比第一次就打卡优，因为中间的一段路程余钱更多。

因此从一个点 $i$ 出来时，剩余的钱不会少于 $c_i=\max\{a_i-b_i,0\}$。从走出来钱最多的点开始 DP。所以按照 $c_i$ 从小到大排序，建立点权重构树。树形 DP 的策略是先走度数减一个子树，然后打卡自己，再走最后一个子树。这样能遍历所有的状态。代码。

网络流

是个很有用的东西。

概念

一个网络是一张有向图 $G=(V,E)$，对于每条有向边 $(u,v)\in E$ 存在容量限制 $c(u,v)$，当 $(u,v)\not\in E$ 时，$c(u,v)=0$。网络的可行流分为有源汇（指定了两个节点 $s,t$，代表图的源点和汇点）和无源汇，但是都存在一个定义域为节点二元组的流函数 $f(x,y)$，$f(x,y)$ 代表边 $x\rightarrow y$ 的流量，满足：

1. $f$ 满足容量限制：$f(x,y)\le c(x,y)$，当两者相等时，$x\rightarrow y$ 就流满了；
2. 斜对称性质：$f(x,y)=-f(y,x)$，也就是说，反向边其实是负的流量；
3. 流量守恒：除源点和汇点外（当然只限于有源汇可以除了这两个节点），从每个节点流入和流出的流量相等，即 $\forall i\ne s,t,\sum f(u,i)=\sum f(i,v)$，也就是说，每个节点不储存流量，进去多少就流出来多少。

下面是一些定义：

• 对于有源汇，有 $\sum f(S,i)=\sum f(i,T)$，此时这个相等的和成为当前流 $f$ 的流量。
• 定义流 $f$ 在网络 $G$ 上的残量网络 $G_f=(V,E_f)$ 为容量函数 $c_f=c-f$。根据容量限制，$c_f(x,y)\ge 0$，当 $c_f(x,y)=0$ 时，则视为 $x\rightarrow y$ 在残量网络上不存在。也就是说，在残量网络中我们要删掉满流边。
• 定义增广路 $P$ 是残量网络 $G_f$ 上源点到汇点的一条路径，而无源汇则没有增广路。
• 将点集分为两个互补相交的 $A,B$，且满足 $S\in A, T\in B$，这种划分方式称为割，割的容量为 $\sum_{u\in A}\sum_{v\in B}c(u,v)$，流量为 $\sum_{u\in A}\sum_{v\in B}f(u,v)$。如果 $u\in A,v\in B$，那么 $(u,v)$ 是割边，可以看出，割边一般不止一条。
• 割中割边容量和最小的划分方式称为最小割，而且最大流等于最小割。

最大流问题

解决最大流问题的思想是：不断寻找增广路 和 能流满就流满。在给一条边增加流量时，我们需要给其反向边来增加容量来支持反悔。这样的操作称为一次增广。

EK 算法的思想是使用 BFS 寻找长度最短的增广路，然后计算流量。为此我们记录流向每个点的边的编号，然后从汇点反推到源点，时间复杂度为 $O(nm^2)$。

Dinic 的本质思想是多路增广和当前弧优化（跳过流满的边）。通过 BFS 将图分层，向下一层节点开始进行多路增广，并记录当且流满到了哪条边。

struct Graph {
    struct Edge {
        int v, w; 
        Edge(int v = 0, int w = 0) : v(v), w(w) {}
    }; 
    vector<Edge> E; 
    vector<int> G[N]; 
    inline void add(int u, int v, int w) {
        E.emplace_back(v, w); G[u].emplace_back(E.size() - 1); 
        E.emplace_back(u, 0); G[v].emplace_back(E.size() - 1); 
    } 
    int S, T, cur[N], d[N], vis[N]; 
    bool bfs(void) {
        memset(cur, 0, sizeof cur); memset(d, -1, sizeof d); 
        queue<int> q; q.push(S); d[S] = 1; 
        while (!q.empty()) {
            int u = q.front(); q.pop(); 
            for (int i = 0; i < G[u].size(); ++i) {
                Edge &e = E[G[u][i]]; 
                if (e.w && d[e.v] == -1) {
                    d[e.v] = d[u] + 1; q.push(e.v); 
                    if (e.v == T) return 1; 
                }
            }
        }
        return 0; 
    }
    int dinic(int x, int res) {
        if (x == T) return res; 
        int flow = 0; vis[x] = 1; 
        for (int i = cur[x]; i < G[x].size() && res; ++i) {
            Edge &e = E[G[x][i]]; cur[x] = i; 
            int c = min(res, e.w); 
            if (!vis[e.v] && d[e.v] == d[x] + 1 && c) {
                int k = dinic(e.v, c); flow += k; res -= k; 
                e.w -= k; E[G[x][i] ^ 1].w += k; 
            }
        }
        if (!flow) d[x] = -1; vis[x] = 0; 
        return flow; 
    }
    int maxFlow(int s, int t) {
        S = s, T = t; 
        int flw = 0, mxflw = 0; 
        while (bfs()) while (flw = dinic(S, 1e9)) mxflw += flw; 
        return mxflw; 
    }
} G; 

只需要将 BFS 改成 SPFA 就可以完成无负环的最小费用最大流，时间复杂度为 $O(nmf)$，其中 $f$ 指最大流流量。

最小割的方案构造是简单的，在残量网络中，$dis_u$ 存在证明其与 $S$ 相连。

上下界网络流

给每条边加入一个流量下界 $b$ 就是上下界网络流。

无源汇可行流

常见问题与模型

网络流有一些常见模型，这里做一下总结。

最小割点

删去点 $i$ 有代价 $w_i$，求使得 $S,T$ 不连通的最小代价。

将每个点拆成入点 $i_{in}$ 和出点 $i_{out}$，在它们之间连一条容量为 $w_i$ 的边，表示删去这个点。对于原图的每一条边 $u,v$，连接 $u_{out}\rightarrow v_{in}$ 一条 $+\infty$ 容量的边，这样我们只能删点而不会割边，实际上就是将边作为了点。

集合划分模型

连 $S\rightarrow i$ 的容量为 $b_i$ 的边，$i\rightarrow T$ 的容量为 $a_i$ 的边。如果割掉了 $i\rightarrow T$，说明将 $i$ 划分到了集合 $A$，代价为 $a_i$。

给 $u,v$ 连容量限制为 $c_{u,v}$ 的双向边，这样如果 $u,v$ 不属于同一集合，至少会割掉其中一条边。

这样这个网络的最小割就是答案。

还有一种限制：$x$ 在集合 $A$ 且 $y$ 在集合 $B$ 时有代价 $w$，那么连 $x\rightarrow y$ 的容量为 $w$ 的边，这样如果 $x$ 和 $S$ 相连且 $y$ 和 $T$ 相连，那么这条边需要被割掉。

如何输出方案？要注意什么是割边：在最后的残量网络上 $d(x)$ 是否存在，存在则属于集合 $A$，否则是集合 $B$。

喜欢关系如何处理？将每个组都建一个点，组 $i$ 在最终的残量网络上与 $S$ 相连则表示合作，与 $T$ 相连则表示不合作。任何一个人不同意这个组就不合作，因此组向它的组员连 $+\infty$ 的边，这样如果这个组与 $T$ 相连，那么便不合作。

将 $B$ 向 $A$ 对应的组连 $a_i$ 的边，这样如果 $B$ 同意了（它没有连向 $T$），$A$ 组没有合作（连向了 $T$），则要割掉 $a_i$。类似地，$B$ 的组向 $A$ 连 $b_i$。代码。

最大权闭合子图

每个点有点权，求闭合子图的最大权值。

考虑集合划分模型，对于每个节点，可以将其划分到选或不选的集合中，也就是 $S\rightarrow i$ 连 $0$，$i\rightarrow T$ 连 $w_i$。如果 $(u,v)\in E$，就是如果 $u$ 分到选的集合中，$v$ 也必须分到选的集合中，即 $u\rightarrow v$ 有容量 $-\infty$，求网络的最大割即可。

但是最大割是 NPH 的，因此考虑取相反数求最小割。然而这样会出现负容量的边！将负容量的边改到 $S\rightarrow i$ 来连。这样答案为所有正权值的和减去最小割，实际上是先将所有正点权选入，然后考虑哪些不选。

切糕模型

Portal.

$n$ 个变量 $x_i$，每个变量的取值范围为 $x_i\in[1,m_i]$，每两个变量之间会对答案产生贡献（一般和两变量差有关），我们要最大化 / 最小化这个贡献。

建图方式一般就是对每个变量 $x_i$ 个点拆成 $m_i$ 个点个点串成一个源点到汇点的链，割哪条边就代表取哪个值，贡献用两条链直接的连边表达，于是就变成最小割形式了。

注意到有一个光滑度限制，可以连一条 $u\rightarrow v$ 的 $+\infty$ 的边。

可以证明，一条链最多割一条边。代码。

最小割树

模板。

DAG 最小路径覆盖

首先 SCC 缩点，一个 SCC 内可以染同一个颜色，那么只需要处理 DAG。

求的是 DAG 最小可交路径覆盖。也就是一个点内部的流量是不限的。

二分图相关

设无向图 $G=(V,E)$，若能够将 $V$ 分成两个点集 $V_1,V_2$ 满足 $V_1\cap V_2=\varnothing,V_1\cup V_2=V$ 且 $\forall(u,v)\in E,u\in V_1,v\in V_2$（也可以反过来），这样 $G$ 是一张二分图，$V_1,V_2$ 分别称为左部点和右部点。

二分图的充要条件是不存在奇环，这样我们可以给二分图进行黑白染色。

从某个点开始 DFS，遍历当前点 $u$ 和邻居 $v$，如果 $v$ 未被访问，则 $v$ 的颜色与 $u$ 相反；如果访问过，说明存在奇环。

二分图匹配

给定二分图 $G=(V,E)$，若边集 $M\subseteq E$ 满足 $M$ 中任意两条边不交于同一端点，则称 $M$ 是 $G$ 的一组匹配，其大小为 $|M|$。

特别的，若 $|V_1|=|V_2|,|M|=|V_1|$，则称 $M$ 为完美匹配。

最大匹配。我们希望求出边集 $M$ 的最大大小。显然，我们从 $S$ 向 $V_1$ 的所有点连一条 $1$ 的边，$V_2$ 向 $T$ 连一条 $1$ 的边，根据 $E$ 从 $V_1$ 向 $V_2$ 连边，跑最大流即可。在这里 Dinic 的时间复杂度为 $O(m\sqrt{n})$。

最大多重匹配。即节点 $u$ 不能与超过 $L_u$ 条边相连，这样只需要将每个点与源点或汇点的容量设为 $L_u$ 即可。时间复杂度依然正确。

带权最大匹配。图中是没有环的，将其转化为最小费用最大流即可。注意这时的时间复杂度没有保证，如果边权范围较小，可以按照边权顺序加边，依次跑最大匹配。

匈牙利算法可以以 $O(nm)$ 的时间复杂度解决二分图的最大匹配问题。

工作过程如下：

• 加入一个左部点 $x$，然后让 $x$ 去尝试匹配。
• 如果 $x$，已经匹配，则增广失败。
• 遍历 $x$ 能到达的所有右部点 $y$：
  • $y$ 被访问过了，那么直接再见。
  • $y$ 没被匹配，让 $x$ 匹配 $y$，增广成功。
  • $y$ 被匹配，考虑 $y$ 原来匹配的 $x'$，如果 $x'$ 还能够成功匹配，那么改为让 $y$ 匹配 $x$，形成新的增广路。

实际上，如果当前点失配，vis 数组是不需要清空的！模板，代码如下：

int n, m, E, mch[505], vis[505];
vector<int> G[505];

bool dfs(int x) {
	if (vis[x]) return 0; vis[x] = 1; 
  	for (int y : G[x])
    	if (!mch[y] || dfs(mch[y])) return mch[y] = x, 1; 
	return 0; 
}

int main(void) {
  	cin >> n >> m >> E;
  	for(int i = 1; i <= E; i++) {
    	int u, v; cin >> u >> v;
    	G[u].push_back(v);
  	}
  	int ans = 0;
  	for (int i = 1; i <= n; i++) if (dfs(i)) {
    	memset(vis, 0, sizeof(vis));
    	++ans; 
  	}
  	cout << ans << endl;
  	return 0;
}

完美匹配是指匹配大小为 $n$，Hall 定理可以用于判定是否存在完美匹配，当且仅当对于任意 $S\subseteq V_1$，均有 $|S|\le |N(S)|$，其中 $N(S)$ 指 $S$ 所连接的右部的点。

点集相关问题

二分图最小点覆盖集的大小与二分图最大匹配相等，最大独立集等于 $|V|$ 减去最小点覆盖集，最大团等于补图的最大独立集。

网络流 24 题

剔除了其中不是网络流的题。有些建模方式很经典，但是大部分题都显得非常老套了。

试题库问题

Portal.

将试题看作左部点，类型看作右部点，每个试题向对应的类型连边。源点向试题连边，类型向汇点连边。

有解仅当最大流为 $m$，方案的输出可以根据哪些边流满来判断。代码。

飞行员配对方案问题

Portal.

二分图最大匹配模板。代码。

圆桌问题

Portal.

二分图最大多重匹配模板。代码。

太空飞行计划问题

Portal.

将仪器和实验抽象成点，就是最大权闭合子图模板。代码。

骑士共存问题

Portal.

将棋盘上的点划分为左部点和右部点，使得骑士的位置和其能走到的位置在不同的点部。这样就成了二分图最大独立集的模板。代码。

最长不下降子序列问题

Portal.

通过 DP 来求解答案，拆点限制一个点的使用次数。代码。

* 最小路径覆盖问题

Portal.

求的是 DAG 的最小不交路径覆盖。

将点拆成左点和右点，进行二分图最大匹配。每次多流上一个，就说明又有一对点连在了一起，答案可以减少 $1$。两部点之间流满的边就是所有被选进路径覆盖的边，DFS 输出答案即可。代码。

魔术球问题

Portal.

枚举数，然后连可以放在一起的数的边，发现就是最小路径覆盖问题。代码。

餐巾计划问题

Portal.

用最大流描述餐巾个数，费用描述代价，将每个餐厅拆成两个点区分两种餐巾，代码。

星际转移问题

Portal.

从 $t$ 扩展到 $t+1$，在转移的太空电梯之间连边，每次再进行增广即可。代码。

分配问题

Portal.

二分图最大权完美匹配，代码。

运输问题

Portal.

二分图最大权完美匹配，代码。

航空路线问题

Portal.

拆点来限制只经过一次，然后求解最大费用最大流即可。代码。

方格取数问题

Portal.

黑白染色，然后二分图最大独立集。代码。

火星探险问题

Portal.

直接拆点，然后 DFS 暴力输出方案。代码。

深海机器人问题

Portal.

和上道题基本一样。代码。

数字梯形问题

Portal.

拆点限制一个点的经过次数，跑费用流即可。代码。

最长 k 可重区间集问题

Portal.

每两个相邻点之间连流量为 $k$ 的边，然后线段之间连流量为 $1$ 的边即可。代码。

最长 k 可重线段集问题

Portal.

特殊处理垂直于 $x$ 轴的线段，让其有长度即可。代码。

例题

一些比较有趣的题。

[CF1728F] Fishermen

Portal.

我们需要构造一个 $a_i\mid b_i$ 且 $b_i$ 互不相同，这样这个 $b$ 就一定是满足条件的。

构造所有的 $k\times a_i,k\in [1,n]$，我们用这些数来匹配 $a_i$。这样点数和边数都是 $O(n^2)$ 的。

考虑匈牙利算法，在找到匹配时清空 vis 数组，由于只有 $O(n)$ 个匹配，因此时间复杂度 $O(n^3)$。代码。

针对图的性质分析

竞赛图

竞赛图有一些性质：

• SCC 缩点后 DAG 呈链状（其中必有一条链），前面的所有点向后面的所有点连边；
• 每一个 SCC 连通块都存在一条哈密顿回路；
• 竞赛图存在一条哈密顿路径；
• 对于一个 SCC，大小为 $[3,siz]$ 的简单环均在其内部存在。

竞赛图判定。令 $s_i$ 为第 $i$ 个点的出度，那么应该满足 $\sum_{i=1}^{k} s_i\ge \binom k 2$ 且 $k=n$ 时等号必须成立。实际上比较显然。

例题

都比较有趣。

* [CF1477D] Nezzar and Hidden Permutations

Portal.

首先度数为 $n-1$ 的点不管顺序怎么定其拓扑序都是定死的，然后得到新的 $n'$ 个度数不超过 $n'-2$ 的点。

这个问题看起来依然不是很能做，相比于原问题条件依然没有弱化掉什么。常用套路，正难则反，取补图，我们就得到了一个每个点度数都大于 $1$ 的图。

对每个连通块求出 DFS 树，然后进行菊花剖分，其中一个先中间再其它，另一个先其它再中间。不难发现这样是满足条件的。剖分菊花时贪心地选取，剩下的点讨论一下是放进别的菊花还是新建菊花即可。代码。

[CF1142E] Pink Floyd

Portal.

首先对粉色边 SCC 缩点，然后考虑入度为 $0$ 的 SCC 中放入一个点到集合 $A$ 中，每次取 $A$ 中两个结点合并。

我们要找到一个入度为 $0$ 的点，因此每次选择两个 SCC 考虑合并，依次干掉其中入度为 $0$ 的点，直到只剩下一个。代码。

针对建图分析

如何建图是一个很有意思的过程。很多问题都可以转化为图论问题，而图论问题也可以通过建图方式变得更好做。

图论问题的建图

拆点拆边。拆点可以很好地对一个点做出限制，比如网络流中常通过拆点对一个点的通过次数做出限制。而拆边则是将边转成点，在点之间行走就是在边之间切换（就是将原图中的点作为边）。

差分建图

边走到边有代价，那干脆把边转成点，一条有向边对应着一个点，两条反向边的边权为原边权（切边的贡献），然后通过枚举中转点的入边出边来建边就可以直接算出贡献，这样的边数是这样的边数是 $O(m^2)$ 的。

常用的优化思路是，将边转化为等效的内容。实际上我们可以对于一个点的出边按照边权从小到大排序后差分依次连接，反着连则是边权为 $0$。这样在从入边切到比入边边权小的出边时就没有额外的贡献，而切到比它大的东西时就会在走这条差分链时产生贡献，刚好可以满足条件。代码。

线段树优化建图

建立两棵线段树，大概像这样：

于是直接在线段树上连边即可。代码。

CDQ 分治优化建图

堆优化存边

其它问题的建图

图论杂项

一些图论杂项知识点。

图的着色

我们讨论无自环图。令 $\Delta(G)$ 为 $G$ 的最大点度数。

相邻点不能同色，最小的能将图染色的数量成为图的点色数。

对于任意图 $G$，其点色数 $\le \Delta(G)+1$。

对于边染色，其满足色数 $\Delta(G)\le k\le \Delta(G)+1$。对于二分图能取到下界，构造的时候直接直接枚举当前两个点没有连接过的最小颜色，如果不同则强制调整成其中的一个。代码。

题车

注重刻画不同建模之间的联系，尝试总结一个对于图论问题的思考手段。

刷基础 1

一些简单题。

[POI2014] RAJ-Rally

Portal.

考虑按照拓扑序 $1\sim n$ 枚举每个点，开始时所有点在 $B$ 集合内，内部有 $n$ 个距离，然后把拓扑序小的点加到 $A$ 集合里，每次维护可以穿过 $A,B$ 集合的距离即可。代码。

[SHCPC2022] Just Some Bad Memory

Portal.

是否存在奇环用二分图，偶环用 Tarjan 是否是仙人掌。

刷基础 2

网络流相关。

[NOI2008] 志愿者招募

Portal.

发现直接按照顺序连边容量为 $+\infty-a_i$ 的边，每个人连 $+\infty$ 的边，代码。

[CF1510B] Button Lock

Portal.

所有数向其子集连边，跑二分图匹配，匹配失败的点就是一个终点。代码。

刷提升

稍有难度的题目。

[省选联考 2020 B 卷] 丁香之路

Portal.

容易发现，起点终点的度数都应该是奇数，路径上其余点的度数是偶数。贪心地把度数为奇数的点和它的下一个点相连；如果这会使下一个点变成奇点，就继续把下一个点和下下一个点相连，以此类推。这样建边的代价一定是最小的，因为新建出的边边权都为 $1$ 且互不相交。这样就满足了上面提到的度数限制。

但还有一个问题：这样建边后图可能会不连通。那么我们把已有的连通块用并查集缩点，然后求最小生成树，让图连通的最小代价就是最小生成树大小的两倍。时间复杂度 $O(n^2\log n)$。代码。

[HNOI2019] 校园旅行

Portal.

考虑暴力，$f_{x,y}$ 是否存在 $x\rightarrow y$ 的回文路径，直接记忆化搜索 $O(n^2 + m^2)$。

问题是我们的边数太多了！注意到路径长度其是不太要紧，因为可以来回走刷分。首先考虑一个事情，如果我只能走同色点，那么我们好像不能改变我们当前刷的路径长度的奇偶性——除非有奇环，即不是二分图。

那么对于二分图的同色连通块，可以只保留一棵生成树（因为子图也是二分图），其它同色连通块可以表示为一棵生成树，然后有一个自环。

而异色点是自然二分图，直接保留生成树即可。代码。

[CF1305G] Kuroni and Antihype

Portal.

$0$ 边及其诡异，因此考虑新建一个 $a_{n+1}=0$，那么令边权为 $a_u+a_v=a_u\operatorname{or} a_v$，求出最大生成树即可。代码。

[NOI2021] 庆典

Portal.

首先 SCC 缩点成一座森林，

刷综合

图论相关综合应用。

[ZJOI2022] 简单题

Portal.

如果图是仙人掌，那么就根题目性质没什么关系了。因此每个点双独立，分析点双的性质。

分析可以得到，最多只有两个环相交，最终结论是一定存在两个点 $S,T$，使得这个点双可以由这两个点之间的若干条不相交的链组成，将其称为杏仁，或者有丝分裂期组成纺锤体的丝状结构（纺锤丝）。

那么对点 $x$ 和 $fa_{fa_x}$ 之间的简单路径权值和和方案数可以直接计算出来（树上前缀积预处理即可），这样可以直接跳到 LCA 然后去讨论。

[CF1835F] Good Graph

Portal.

无解直接 Hall 定理判断即可。

对于有解，设 $S_i$ 代表 $i$ 的最小紧密集合，那么任意一个 $S$ 都是由若干个 $S_i$ 并起来的。

对于 $S_i$，其本质是从 $i$ 开始不断地跑交替路，然后跑到一定程度它会闭合。也就是说，对于原图上的左部点 $i$，右部点存在一条边 $(i,j)$，我们只需要在 $mch_i\ne j$ 时，连一条 $i\rightarrow mch_j$ 的边，因为它们需要在同一个 $S$ 内。

也就是说我们要找一张最小图使得和原图传递闭包相同，先 bitset 求出，SCC 内部连环，外面依次连接即可。

还原到原二分图上，剩下的部分连接上 $i\rightarrow mch_i$ 即可。代码。