图论复习～

最悪の記者2

给定序列 \(A,B,C,D\)，需要你通过若干次对 \(A,C\) 的单点修改操作，使得存在一个排列 \(p\)，对于所有 \(1 \le i \le n\)，\(A_i=C_{p_i}\) 且 \(B_i \le D_{p_i}\)，保证有解。求修改次数最小值。

\(1 \le n \le 2 \cdot 10^5\)，\(1 \le A_i,C_i \le n\)，\(1 \le B_i,D_i \le 10^9\)，\(B,D\) 单调递减。

题意转化，使 \((A_i,B_i)\) 为左部点，\((C_i,D_i)\) 为右部点，则左右均有 \(n\) 个点，左右点有边必须满足 \(B_i\le D_j\)，连边的权值为 \([A_i \neq C_j]\) 的二分图的完美匹配的最小权值。（约定 \(N(S)\) 为左部点集合 \(S\) 连接的所有右部点集合）

边权只有 \(0/1\)，尝试贪心选取，按 \(B\) 从大到小枚举左部点，尽量选 \(0\) 边。但这样显然是错的，因为直接选择 \(0\) 边可能会导致后面的点无边可选，因此选之前必须先用 Hall 定理判一下，用线段树维护 Hall 定理就好了。

使用 Hall 定理判定完美匹配：\(\forall S \subseteq [n]，|N(S)| \ge |S|\)，定理中要求所有子集都满足，但由于这题的性质：\(\forall B_i > B_j,N(\{i\}) \le N(\{j\})\)，显然越靠前的点限制越紧，如果左部点的所有前缀子集 \(S\) 均满足 \(|N(S)| \ge |S|\)，那么所有子集都满足这个条件了，证明显然。

Baltazar

给定一张边带权的图，求有多少条边满足：将该边的权值增加 \(2\) 后，\(1 \to n\) 最短路增加 \(1\)。

多测，\(1 \le \sum n,\sum m \le 3\cdot 10^5\)。

先跑最短路，求出以 \(1\) 到每个点的距离 \(d_i\)。那么增加长度的这条边 \((u,v,w)\) 满足是最短路图（即连接所有满足 \(d_u+w=d_v\) 的 \((u,v,w)\)）上的一条边且将 \(1,n\) 分割开。显然这只是一个必要条件。

跑最短路时顺便再跑一个严格次短路，跑出一个次短路的分层图，那么这条边还必须满足不为 \(1,n'\) 的割边。

跑 \(2\) 次 \(\tt tarjan\) 就完了。

至于最短路图如何建，应该是熟悉的。

而次短路图的建法，我们先要了解次短路图的定义：满足其中所有边均可存在于 \(1\rightsquigarrow n\) 的次短路的路径上的一张子图。

首先单源次短路求出 \(d'_n\) 的大小，接下来从 \(u=n,l=d'_n\) 开始，通过 dfs 递归地处理次短路图：

接受 \(u,l\) 参数：表示当前处理 \(1 \rightsquigarrow u\) 的次短路图，次短路长度为 \(l\)。

枚举 \((u,v,w) \in E\)：

• \(d_v+w=l\)，说明这条边可以出现在 \(1 \rightsquigarrow v \to u\) 的路径上，递归处理 \(1 \rightsquigarrow v\) 的次短路图，长度为 \(d_v=l-w\)。
• \(d'_v+w=l\)，说明这条边可以出现在 \(1 \rightsquigarrow v \to u\) 的路径上，递归处理 \(1 \rightsquigarrow v\) 的次短路图，长度为 \(d_v'=l-w\)。
• 可以证明 \(k\) 短路（\(k \ge 3\)）不可能对次短路图产生影响，只处理到次短路即可。

精准打击 / Kontrmanifestacja

求有向图中所有回路点集之交。

\(1\le n\le 5 \cdot 10^5, 1\le m \le 10^6\)

什么时候才会分析性质呢？🤔 🤔 🤔 🤔 🤔 🤔 🤔 🤔

如果图本身是 DAG，输出 NIE。这个很好判断。

本题的等价描述是有向图中存在多少个点：删去该点后，有向图变为 DAG。

但是 DAG 就是依托使，除了能 DP 就没有什么有用的性质了。

还是考虑回到原定义：由于是交，所以任意一个环上是包含了所有在交集中的点的；可以通过简单的处理得到一个环。

考虑这个环上哪些点不会成为交集中的点；显然，除去这个环后，剩余图若不是 DAG，就存在另一条与该环不交的环，交集为 \(\varnothing\)；所以特判之后剩余图是个 DAG。

但是由于上文所述，DAG 就是一坨结构，重心还是回归环上。如果能从环上节点 \(S,T\) 通过 DAG 绕过环上 \(S \rightsquigarrow T\) 之间的节点，那么 \(S \rightsquigarrow T\) 之间的节点就全废了。显然，如果找不到这样的 \(S,T\) 去覆盖它的节点就一定是交集中的点。

当寻这样的点 \(S,T\)。断环成链后，确定 \(S\) 可以找到 \(T_{\max}\)，于是 \(T_{\max}\) 是向后最大覆盖范围；然而 \(T_{\min}\) 则不是。所以考虑跑反图，从 \(T\) 找 \(S_{\max}\) 即可。

图中：紫色部分表示被不合法的点，蓝色、绿色部分表示一条回路（回路之外的均不合法）

观察到 \(T_{\max}\) 的情况当然是编号越大的时候，砍掉的点范围越大，所以 \(\max\) 是合理的。然而 \(T_{\min}\) 的情况砍掉的点范围却不如 \(T_0\)，因此并不是越小越好。既然如此，直接反连原图，枚举 \(T_0\) 寻找 \(S_{\max}\) 就是一种好的想法。

[CCPC 2023 北京市赛] 哈密顿

注：实际为贪心练习。

给定权值 \(a_i, b_i\)，求 \(i \to j\) 的连边长度为 \(|a_i-b_j|\) 的完全图的最长长度的哈密顿回路。

\(n \le 10^5, a_i,b_i \le 10^9\)。

从绝对值入手分析，拆成点贡献，由于哈密顿回路中每个点只连 \(2\) 条边，令 \(i \to j \to k\)：

\[|a_i-b_j|+|a_j-b_k|= \max\begin{cases} a_i-b_j+a_j-b_k&\text{Case 1}\\ a_i-b_j+b_k-a_j&\text{Case 2}\\ b_j-a_i+a_j-b_k&\text{Case 3}\\ b_j-a_i+b_k-a_j&\text{Case 4} \end{cases} \]

\(j\) 点贡献：

• Case 1：\(+a_j-b_j\)
• Case 2：\(-a_j-b_j\)
• Case 3：\(+a_j-b_j\)
• Case 4：\(+a_j+b_j\)

观察：

1. 所有点的贡献可以均为 Case 1，也可以均为 Case 3。
2. 绝对值取正负号个数相等，即取 Case 2 贡献次数等于取 Case 4 贡献次数。
3. 若同时存在 Case 1，Case 3，那么至少存在 \(1\) 对 Case 2+Case 4。
4. 考察取法是否一定可以构造一个哈密顿回路：
   • 由于是求答案的最大值，同时绝对值 \(|a-b|=\max \{a-b,b-a\}\)，直接拼点贡献得到的最大值一定是最优合法路径的点贡献之和。

特判掉 1.，然后将贡献最大的 Case 1，Case 3 加入答案，接下来用优先队列维护往里面加 Case 2，Case 4 对就好了。