最大点权最大匹配问题

qiminghaonan · 2026-08-25 16:34:26 · 算法·理论

最大点权最大匹配问题在算法竞赛领域较为冷门，柯绎思在他的 2024 国家集训队论文里曾经有所提及，可惜他主要聚焦于将一般图最大点权最大匹配规约为二分图最大点权最大匹配问题的方法，而将本文主要涉及的二分图最大点权最大匹配算法当作黑盒调用。本文将从刻画最大匹配的经典图论定理入手，介绍二分图最大点权最大匹配算法和一般图上的算法。虽然洛谷上目前一共大约有两道题可以用这个算法做，但是不改这些结构定理的重要性。

Dulmage-Mendelsohn 分解定理和二分图最大点权最大匹配问题

Dulmage-Mendelsohn 分解定理

给定二分图 G = (S,T,E) 和它的一个最大匹配 M，可以将顶点集合 V 分为三个子集：\mathcal E 为从未匹配点出发，经过长度为偶数的交错路可达的点；\mathcal O 为从未匹配点出发，经过长度为奇数的交错路可达的点；\mathcal U 为从未匹配点出发，经过交错路不可达的点。熟知这三个子集满足以下性质：

• 取 G 的三个子图 (\mathcal U, \mathcal U) (\mathcal E, \mathcal O) (\mathcal O, \mathcal E)，则 G 的任意最大匹配都包含于这三个子图的并。

据此可得，对于任意的最大匹配 M_1, M_2，M_1 匹配的左部点和 M_2 匹配的右部点之间存在完美匹配。

:::info[证明]

取 M_1 \cap (\mathcal U, \mathcal U) 或 M_2 \cap (\mathcal U, \mathcal U)，M_1 \cap (\mathcal E, \mathcal O)，和 M_2 \cap (\mathcal O, \mathcal E) 的并即可。

:::

于是我们可以将二分图最大点权最大匹配问题拆分成两个单边带权的二分图最大点权最大匹配问题。

单边带权二分图最大点权最大匹配问题

贪心算法

单边带权二分图最大点权最大匹配问题存在贪心算法。维护一个匹配，初始为空；将点按权值从大到小排序，依次执行：若从此点出发存在增广路，则沿它增广；否则无事发生。证明略。

在一般情况下，这个算法的复杂度是 O(n^2)，较为优秀。它的最大局限是，如果图的结构简单，并不能降低复杂度，所以我们有寻求更加优秀的算法的动力。

分治算法

分治算法的核心思想是：每次加一个点尝试增广效率太低，能不能一次添加一批点？答案是可行的，而这依赖于引理 2：记二分图 (S,T,E) 上有点权函数 w(S)，满足一个技术性条件：任意两点的权值不同。记 S_k 表示点权最大的 k 个点组成的集合，且子图 (S_k, T) 的 Dulmage-Mendelsohn 分解为 (\mathcal U, \mathcal O, \mathcal E)，则整个图的最大权最大匹配包含于以下三个子图的并：(\mathcal U \cap S_k, \mathcal U \cap T)(\mathcal E \cap S_k, \mathcal O \cap T)((\mathcal O \cap S_k) \cup (S \backslash S_k), \mathcal E \cap T)。换句话说，S \backslash S_k 只能与 \mathcal E \cap T 匹配。同时，\mathcal O \cap S_k 的点已确定包含于第三个子图的最大权最大匹配。

:::info[证明]

考虑应用贪心算法。既然任意两点的权值不同，贪心算法的执行顺序就是唯一的。在前 k 个点执行结束时，得到 (S_k, T) 的最大权最大匹配，其结构受 Dulmage-Mendelsohn 分解定理节制。这表明目前的最大权最大匹配一定已经匹配了 \mathcal O \cap S_k 的所有点。既然增广路只会增大匹配点集，\mathcal O \cap S_k 的匹配情况维持。只需证明每新增一个节点时，增广路会被限制在 ((\mathcal O \cap S_k) \cup (S \backslash S_k), \mathcal E \cap T) 子图内即可。

考虑找增广路的过程。

• 若沿非匹配边走到 \mathcal U \cap T，则此点必被匹配，会沿匹配边走到 \mathcal U \cap S_k，然后沿非匹配边走到 \mathcal U \cap T 或 \mathcal O \cap T。
• 若沿非匹配边走到 \mathcal O \cap T，则此点必被匹配，会沿匹配边走到 \mathcal E \cap S_k，然后沿非匹配边走到 \mathcal O \cap T。
• 若沿非匹配边走到 \mathcal E \cap T，且此点未被匹配，则找到增广路。
• 若沿非匹配边走到 \mathcal E \cap T，且此点被匹配，则可能沿匹配边走到 \mathcal O \cap S_k 或 S \backslash S_k，然后沿未匹配边可能走到 T 中的任意一部分。

把所有可能性都列出之后，容易发现增广路的唯一可能形态是不断在 (\mathcal O \cap S_k) \cup (S \backslash S_k) 和 \mathcal E \cap T 之间来回，即被限制在上述子图内。

:::

然后考虑如何利用该引理进行分治。如果每次简单粗暴取 k = \tfrac {|S|}{2} 是不合适的，因为最坏情况下，会出现 \mathcal O = S_k，\mathcal E = T 这种情况，此时分治了等于没分治。但是，即使在这种情况下我们也可以从中提取信息：S 中前一半重的点都已确定进入最大权最大匹配（简记：确定点）。换句话说，还不确定是否进入最大权最大匹配的左部点（简记：未知点）数量减半。这提示我们：可以记录一个额外参数 u，表示未知点数量。显然，它们是 S 中权值最小的 u 个。然后我们取 k = n - \tfrac{u}{2}，即选择 S_k 包含未知点的前一半以及确定点的所有。然后考虑分成的三个子图的左部。

综上所述，分治下去的两部分的未知点数量都至少减半，也就是说 O(\log n) 层分治即可到达底层：u = 0 或 u = 1。若 u = 0，则表明最大匹配能把所有左部点匹配上；若 u = 1，则只需再求一次最大匹配，如果匹配上了所有左部点，那么直接成功；反之则说明最大匹配的大小是左部点数量减一，此时扔掉那个唯一的未知点（现在知道了不行）即可。

接下来计算算法的复杂度：显然，这个算法每次会调用求解最大匹配和 Dulmage-Mendelsohn 分解的算法作为黑盒子程序，以及进行取子图操作。递归过程中，每层的若干子图都是无交的，并且包含于原本的 G。那么，如果上述操作的时间复杂度为 O(f(G))，且 f(G) 是单调凸的（正常的时间复杂度函数都满足），也就是对于 G_1 \subseteq G_2 有 f(G_1) \leq f(G_2) 以及 G = G_1 + G_2 满足 f(G_1) + f(G_2) \leq f(G)，简单放缩可得每层的总时间复杂度是 O(f(G))，总时间复杂度为 O(f(G) \log n)。但是对于空间，如果子程序的空间复杂度是 O(h(G)) 且 h(G) 单调凸，递归算法的时间复杂度仍取决于实现方法：如果是递归实现，则因为占用空间不能保证每层减半，空间仍是 O(h(G) \log n)；但如果采用非递归的实现，可以做到自上而下遍历递归树，同一时刻只需存储 O(1) 层的信息，故而空间可以压缩到 O(h(G))。

备注：实际上甚至不需要求出完整的 Dulmage-Mendelsohn 分解也能实现这个分治算法。注意到 \mathcal U 存在完美匹配，并且可以加入任意另一子图而不影响分析；换言之，求出 (\mathcal E \cap S_k, \mathcal O \cap T) 或者 (\mathcal O \cap S_k, \mathcal E \cap T) 包含的顶点即可正确地分治。

Gallai-Edmonds 分解定理和一般图最大点权最大匹配问题

考虑将 Dulmage-Mendelsohn 分解定理推广到一般图。Gallai-Edmonds 分解依然可以依托一个最大匹配建立。因为花结构的存在，我们必须要求交错路是简单的。此外，因为直觉上我们希望一朵花里的点地位相当，但是一朵花里，除了花根都能同时被奇偶交错路抵达，但花根不一定能被奇交错路抵达，所以我们应该把点分为三类：能沿偶交错路抵达的，能且仅能沿奇交错路抵达的，以及不能抵达的。一般文献中，这三类点集分别称作 \mathcal D, \mathcal A, \mathcal C。

仿照 Dulmage-Mendelsohn 分解定理，尝试证明这个点集的性质。有两条性质是显然的。

• 边集里不包含 \mathcal D - \mathcal C 边。

然后从最大匹配必须点切入。

:::info[证明]

考虑反过来证明非必须点集合和 \mathcal D 的关系。如果 x \in \mathcal D，则将最大匹配沿这条偶交错路翻转即可获得另一个最大匹配，且 x 未匹配；如果存在最大匹配 M' 满足 x 未匹配，则考虑 M \Delta M' 的形态，x 必然在一个偶路径的一端，此偶路径即为 M 的偶交错路。

:::

这样就证明了 \mathcal D 与最大匹配的选取无关。进一步地

:::info[证明]

对于任意的 x \in \mathcal A，显然 x \in N(\mathcal D) 及 x \notin \mathcal D，即 \mathcal A \subseteq N(\mathcal D) \backslash \mathcal D。反过来，如果 x \in N(\mathcal D) \backslash \mathcal D，设 x 与 y \in D 相邻。如果 x 出现在到 y 的偶交错路上，说明 x 可达；如果不出现，则此交错路可进一步沿未匹配的 y-x 边延伸到 x。综上都有 x \in \mathcal A，即 N(\mathcal D) \backslash \mathcal D \subseteq \mathcal A.

:::

马上推出

为什么不先证明这一点呢？其实是因为简单交错路这一限制会导致翻转两个匹配的对称差这一操作对交错路的改变过于复杂，原则上确实可以直接证明，但我没找到简单的思路。此后将会更多地使用最大匹配必须点等性质刻画 \mathcal D, \mathcal A, \mathcal C 集合。在研究最大匹配的性质之前，还需要如下引理：

• 若 u \in \mathcal D(G)，则 \mathcal D(G - u) \subseteq \mathcal D(G) - u, \mathcal A(G - u) \subseteq \mathcal A(G), \mathcal C(G - u) \supseteq \mathcal C(G)。
• 若 u \in \mathcal A(G)，则 \mathcal D(G - u) = \mathcal D(G), \mathcal A(G - u) = \mathcal A(G) - u, \mathcal C(G - u) = \mathcal C(G)。
• 若 u \in \mathcal C(G)，则 \mathcal D(G - u) \supseteq \mathcal D(G), \mathcal A(G - u) \supseteq \mathcal A(G), \mathcal C(G - u) \subseteq \mathcal C(G) - u。

:::info[证明]

• 因为 u 不是 G 的最大匹配必须点，可令 M 为 G 的一个不包含 u 的最大匹配，也是 G - u 的最大匹配。因为移除点 u 不会增加交错路只会破坏，马上推出 \mathcal D(G - u) \subseteq \mathcal D(G) - u 和 \mathcal C(G - u) \subseteq \mathcal C(G)。取 v \in \mathcal A(G - u)，则存在 w \in \mathcal D(G - u) 与其相邻。此时 w \in \mathcal D(G)，故而欲证 v \in \mathcal A(G)，只需证 v 是 G 的最大匹配必须点。反证：令 M_1 为 G 的最大匹配且不包含 v，再令 M_2 为 G - u 的一个不包含 w 的最大匹配，那么它是 G 的一个不包含 u,w 的最大匹配。M_1 \Delta M_2 由偶路径和偶环组成，且某条路径 P 从 v 开始（M_2 不包含 v 的情况下，认为 P = \varnothing）。M_2 \Delta P 是一个不包含 v,u 或不包含 v,w 的 G 的最大匹配，但二者都不可能：若它不包含 v,u，则 M_2 \Delta P 是 G - u 的最大匹配，它不包含 v 和 v \in \mathcal A(G - u) 矛盾；若它不包含 v,w，则可添加边 (v,w)，从而不是最大匹配。
• 只需证明 \mathcal D(G - u) = \mathcal D(G)。因为 u 是 G 的最大匹配必须点，故而任取 M 为 G 的最大匹配包含边 (u,v)，则 M - (u,v) 是 G - u 的最大匹配。比较交错路：(G,M) 的交错路如果不包含 u，则也是 (G - u, M - (u,v)) 的交错路；如果包含，则 u 的下一个点一定是 v，故而可以用 v 开始的交错路代替；这推出 \mathcal D(G) \subseteq \mathcal D(G - u)。反过来，令 v \in \mathcal D(G - u)，再取 w \in D(G) 与 u 相邻，M_1 是 G 的不包含 w 的最大匹配，M_2 是 G - u 的不包含 v 的最大匹配。仍然考虑 M_1 \Delta M_2 里 v 出发的路径 P。
  • 如果 P = \varnothing，说明 M_1 不包含 v，故 v \in \mathcal D(G)。
  • 如果 P 的最后一条边属于 M_1，则 P 是相对于 M_2 的增广路，但 M_2 又是 G - u 的最大匹配，唯一可能是 P 的另一端是 u。此时从 w 出发走 w-u-P^{-1}-v 是相对于 M_1 的偶交错路，故 v \in \mathcal D(G)。
  • 如果 P 的最后一条边属于 M_2，则 P^{-1} 是相对于 M_1 的偶交错路，故 v \in \mathcal D(G)。
• 同理去除匹配边和比较交错路可得 \mathcal D(G - u) \supseteq \mathcal D(G) 以及 \mathcal C(G - u) \subseteq \mathcal C(G) - u。令 v \in \mathcal A(G)，根据上一条引理知道 \mathcal C(G - v) = \mathcal C(G)，即 u 仍是 G - v 的最大匹配必须点。故而 G - v - u 的最大匹配数比 G - v 少一，比 G 少二，进而比 G - u 少一。换言之，v 是 G - u 的最大匹配必须点。但 \mathcal C(G - u) \subseteq \mathcal C(G) - u 所以不能是 v \in \mathcal C(G - u)，只能是 v \in \mathcal A(G - u)。

:::

有了上述引理之后，即可进一步刻画 \mathcal D, \mathcal A, \mathcal C 集合和最大匹配。

• 若将 \mathcal D 的每个连通块缩为一点，并重新连接它们与 \mathcal A 的边，所得的二分图 (\mathcal A, \mathcal D') 的 Dulmage-Mendelsohn 分解满足 \mathcal O = \mathcal A, \mathcal E = \mathcal D', \mathcal U = \varnothing。

:::info[证明]

• 对于任意的最大匹配，\mathcal C 只包含匹配点，而对于任意一条匹配边，若一点可被奇/偶交错路访问，则另一点可被偶/奇交错路访问，从而 \mathcal C 中的点只能匹配另一个 \mathcal C 中的点，即被完美匹配。从而显然连通块大小为偶数。
• 根据之前证明的引理，可以将 \mathcal A 中的点一个一个删除而不改变剩下的点的性质，故而只需要研究所有点都是 \mathcal D 的连通图 G' 的性质。对于其中任意一点 u，再将 u 删除，用引理得知 \mathcal A(G' - u) = \varnothing。此外，根据 \mathcal D(G' - u) 与 \mathcal C(G' - u) 不相邻，G' - u 的每个连通块包含于 \mathcal D(G' - u) 或包含于 \mathcal C(G' - u)。G' - u 的最大匹配数等于 G'，故而所有与 u 相邻的点都是 G' - u 的最大匹配必须点，那么 G' - u 的每个连通块都包含于 \mathcal C(G' - u)，即 G' - u 存在完美匹配。从而显然连通块大小为奇数。
• 对于任意的最大匹配，在上述删除 \mathcal A 中的点的过程中，每次只需同步删除匹配该点的边即可保持为剩余图的最大匹配。而删完之后，剩余图的最大匹配显然是 \mathcal C 的每个连通块的一个完美匹配和 \mathcal D 的每个连通块的一个近完美匹配。
• 对于 G 的最大匹配 M，其包含的 \mathcal A - \mathcal D 边可以对应到 (\mathcal A, \mathcal D') 的边集 M'，显然后者是二分图最大匹配。同时，注意到 M 的交错路只能沿非匹配边离开 \mathcal D 的连通块，再沿匹配边进入 \mathcal D 的另一个连通块，并且离开一个连通块之后就无法再次进入，这表明 M 的交错路也可以对应到 M' 的交错路，马上推出 (\mathcal A, \mathcal D') 的所有点都是交错路可达，故而 \mathcal O = \mathcal A, \mathcal E = \mathcal D', \mathcal U = \varnothing。

:::

这就是 Gallai-Edmonds 分解定理。因此，求出原图的最大匹配之后，可以将最大权最大匹配问题转化为二分图 (\mathcal A, \mathcal D') 上的最大权最大匹配问题，其中 \mathcal D' 的点权为对应连通块中的最小点权，其余点权都直接计入答案。若最大匹配已知，在最大匹配上运行一次带花树算法，即可在 O(n^2) 时间内求出 Gallai-Edmonds 分解，而后续处理包括二分图最大点权最大匹配都可在 O(n^2) 时间内解决。换言之：若一个最大匹配已知，则一般图最大点权最大匹配可在 O(n^2) 时间内求出。

附：一般图上的贪心算法

其实一般图的最大点权最大匹配也可用如下贪心算法求解：维护一个点集和其导出子图上的匹配，初始为空；将点按权值从大到小排序，依次执行：先将此点加入导出子图，然后若从此点出发存在增广路，则沿终点权值最大的增广路增广；否则无事发生。给出证明如下。

只需证明若原图中 M 是最大权最大匹配，则添加点 x 之后仍是最大权最大匹配。

• 如果添加一点之后不会增加增广路，则最大匹配大小不变。对于新图的任意最大匹配 M'，若 M' 不包含 x，由归纳假设，w(M) \geq w(M')；若 M' 包含 x，则 M \Delta M' 包含一条从 x 开始的偶交错路 P，令其终点为 y，则 w(y) \geq w(x)，故 w(M' \Delta P) \geq w(M')，再用归纳假设得 w(M) \geq w(M' \Delta P)，由传递性即得 w(M) \geq w(M')。
• 如果添加一点之后增加了增广路，则最大匹配大小加一，且 x 是最大匹配必须点。对于新图的任意最大匹配 M'，设此图包含边 (x,y)，则 M' - (x,y) 是原图的最大匹配，M \Delta (M' - (x,y)) 包含一条从 y 开始的偶交错路 P，令其终点为 z。则 (x,y) + P 是相对于 M 的增广路，终点为 z。根据归纳假设，w(M) \geq w((M' - (x,y)) \Delta P) = w(M' - (x,y)) + w(y) - w(z) = w(M') - w(x) - w(z)。之前证明了存在相对于 M 的增广路从 x 到 z，故而算法实际找到的增广路 P' 的终点 u 肯定满足 w(u) \geq w(z)，进而 w(M \Delta P') = w(M) + w(x) + w(u) \geq w(M) + w(x) + w(z) \geq w(M')，结论得证。

此算法的时间复杂度和普通带花树相同，为 O(n^3)。

贪心算法的正确性和以下事实强相关：一般图中，其最大匹配覆盖的点集组成拟阵的基。这是匹配极其重要的性质，但由于篇幅原因，这里不再赘述了。之前引理“若 u \in \mathcal D(G)，则 \mathcal D(G - u) \subseteq \mathcal D(G) - u, \mathcal A(G - u) \subseteq \mathcal A(G), \mathcal C(G - u) \supseteq \mathcal C(G)”的证明事实上已经反映了拟阵思想。

例题

我拼尽全力也只找到两道权值在点上的二分图匹配，而且都是同一个情况：凸二分图，也就是说一边的点连向另一边的区间。此时的最大匹配存在贪心算法：将区间按右端点从小到大排序，然后每个区间选择最左的未匹配点进行匹配。最左的未匹配点可以通过并查集维护；求 Dulmage-Mendelsohn 分解的时候，从未匹配的区间开始搜索，寻找区间内的已匹配点匹配上的区间，找到 (\mathcal E \cap S, \mathcal O \cap T)。为了防止一个点被反复找到，可以再用一下并查集。上述过程理论上都可以做到线性，但是我不想写线性并查集了，所以只用了路径压缩。这种题最烦的其实是每次取子图的时候都要重新编号。

P14718 [RMI 2025] 松鼠 / Squirrel

这题里点的数量是 n，但是区间的数量是平方级的，所以朴素的贪心算法可以很好地平衡复杂度，做到 O(n^2)，但是分治算法就只能做到 O(n^2 \log n) 了，感觉拉完了，但是还是可以过，甚至递归的 O(n^2 \log n) 空间也没爆。值得一提的是利用平衡复杂度的思想可以写出一个 O(|S|+|T|^2) 的算法求最大匹配和 Dulmage-Mendelsohn 分解，跑得比路径压缩并查集稍微快一点点。

:::success[AC 代码]

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
using namespace std;

void solve(int N, vector<vector<int>> A, long long& answer, vector<int>& solution) {
  struct leftnode {
    int l, r, val;
  };
  int sz = N * (N + 1) / 2;

  vector<leftnode> l;
  l.reserve(sz);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= i; j++) {
      l.push_back({j, i, A[i][j]});
    }
  }

  vector<int> nxt(N + 1);

  vector<leftnode*> mcm_solution(N);
  const auto mcm = [&nxt, &mcm_solution](const vector<leftnode*>& l, int r) {
    fill(mcm_solution.begin(), mcm_solution.begin() + r, nullptr);
    fill(nxt.begin(), nxt.begin() + r + 1, 0);
    for (auto ptr: l) {
      int x = ptr->l + nxt[ptr->l];
      if (x <= ptr->r) {
        mcm_solution[x] = ptr;
        do {
          nxt[x] = nxt[x + 1] + 1;
          x--;
        } while(x >= 0 && nxt[x]);
      }
    }
  };

  vector<unsigned char> label(sz);
  vector<int> proj[2][2]{vector<int>(N), vector<int>(N), vector<int>(N), vector<int>(N)};
  const auto mwm = [&mcm, &mcm_solution, &label, &nxt, &proj, data_ptr = l.data()]
      (const auto& self, const vector<leftnode*>& l, int u, const vector<leftnode**>& fillback) {
    if (l.empty() || fillback.empty()) return;
    int r = fillback.size();
    vector<leftnode*> solution;
    int uu = u / 2;
    auto cmp = [] (leftnode* a, leftnode* b) {
      return a->val > b->val;
    };
    if (u <= 1) {
      mcm(l, r);
      if (count_if(mcm_solution.begin(), mcm_solution.begin() + r, identity{}) == (ptrdiff_t)l.size()) {
        for (int i = 0; i < r; i++) {
          *fillback[i] = mcm_solution[i];
        }
        return;
      } else {
        auto it = max_element(l.begin(), l.end(), cmp);
        vector<leftnode*> ll;
        ll.reserve(l.size() - 1);
        for (auto it1 = l.begin(); it1 != l.end(); ++it1) {
          if (it1 == it) continue;
          ll.push_back(*it1);
        }
        mcm(ll, r);
        for (int i = 0; i < r; i++) {
          *fillback[i] = mcm_solution[i];
        }
        return;
      }
    }
    vector<leftnode*> ll(l);
    nth_element(ll.begin(), ll.end() - u, ll.end(), cmp);
    auto val2 = ll.end()[-u];
    nth_element(ll.end() - u, ll.end() - uu, ll.end(), cmp);
    auto val = ll.end()[-uu];
    copy_if(l.begin(), l.end(), ll.begin(), [&cmp, val] (leftnode* x) { return cmp(x, val); });
    ll.resize(ll.size() - uu);
    mcm(ll, r);
    vector<leftnode*> even;
    even.reserve(ll.size());
    for (auto ptr: l) {
      label[ptr - data_ptr] = false;
    }
    for (auto ptr: ll) {
      label[ptr - data_ptr] = true;
    }
    for (int i = 0; i < r; i++) {
      if (mcm_solution[i]) label[mcm_solution[i] - data_ptr] = false;
    }
    for (auto ptr: ll) {
      if (label[ptr - data_ptr]) {
        even.push_back(ptr);
      }
    }
    fill(nxt.begin(), nxt.begin() + r + 1, 0);
    while (!even.empty()) {
      const auto ptr = even.back();
      even.pop_back();
      label[ptr - data_ptr] = true;
      int lst = -1;
      for (int x = ptr->l + nxt[ptr->l]; x <= ptr->r; x = x + 1 + nxt[x + 1]) {
        if (label[mcm_solution[x] - data_ptr]) continue;
        label[mcm_solution[x] - data_ptr] = true;
        even.push_back(mcm_solution[x]);
        lst = x;
      }
      if (lst != -1) {
        do {
          nxt[lst] = nxt[lst + 1] + 1;
          lst--;
        } while(lst >= ptr->l || (lst >= 0 && nxt[lst]));
      }
    }
    vector<leftnode**> nxtback[2];
    vector<int> iii[2];
    for (int i = 0; i < r; i++) {
      bool ok = mcm_solution[i] && label[mcm_solution[i] - data_ptr];
      nxtback[ok].push_back(fillback[i]), iii[ok].push_back(i);
    }
    vector<leftnode*> nxtl[2];
    for (int t = 0; t <= 1; t++) {
      auto it = iii[t].begin();
      for (int i = 0; i < r; i++) {
        while (it != iii[t].end() && i > *it) ++it;
        proj[t][0][i] = (it == iii[t].end() ? 1'000'000'000 : it - iii[t].begin());
      }
      auto it2 = iii[t].rbegin();
      for (int i = r - 1; i >= 0; i--) {
        while (it2 != iii[t].rend() && i < *it2) ++it2;
        proj[t][1][i] = (it2 == iii[t].rend() ? -1 : it2.base() - iii[t].begin() - 1);
      }
    }
    int l0 = 0, l1 = 0;
    for (auto ptr: l) {
      if (label[ptr - data_ptr]) {
        ptr->l = proj[1][0][ptr->l];
        ptr->r = proj[1][1][ptr->r];
        if (ptr->l <= ptr->r) {
          nxtl[1].push_back(ptr);
          l1 += !cmp(ptr, val2);
        }
      } else {
        ptr->l = proj[0][0][ptr->l];
        ptr->r = proj[0][1][ptr->r];
        if (ptr->l <= ptr->r) {
          nxtl[0].push_back(ptr);
          l0 += !cmp(ptr, val);
        }
      }
    }
    self(self, nxtl[0], l0, nxtback[0]);
    self(self, nxtl[1], l1, nxtback[1]);
  };

  vector<leftnode*> l_(sz);
  iota(l_.begin(), l_.end(), l.data());
  vector<leftnode*> sol(N);
  vector<leftnode**> sol_(N);
  iota(sol_.begin(), sol_.end(), sol.data());
  mwm(mwm, l_, sz, sol_);
  solution.resize(N);
  answer = 0;
  for (int i = 0; i < N; i++) {
    if (sol[i]) {
      answer += solution[i] = sol[i]->val;
    }
  }
}

int main() {
  int n;
  long long answer;
  vector<int> solution;
  cin >> n;
  vector<vector<int>> A(n);
  for (int i = 0; i < n; i++) {
    A[i].resize(i + 1);
    for (int j = 0; j <= i; j++) {
      cin >> A[i][j];
    }
  }
  solve(n, A, answer, solution);
  cout << answer << endl;
  for (int i = 0; i < n; i++) cout << solution[i] << ' ';
  cout << endl;
}

:::

P8021 [ONTAK2015] Bajtman i Okrągły Robin

这题就厉害了，因为真的可以做到 O(n \log n)，但是这个朴素的并查集似乎跑不过 乱搞 。

:::success[AC 代码]

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

struct leftnode {
  int l, r, val;
};

int solve(const vector<leftnode*>& l, int N, const leftnode* data_ptr) {
  int sz = l.size();

  vector<int> ufds(N + 1);
  vector<int> stk(N + 1);
  auto fnd = [&ufds, &stk] (int x) {
    int tp = 0;
    while (ufds[x] != x) {
      stk[tp++] = x;
      x = ufds[x];
    }
    while (tp) {
      tp--;
      ufds[stk[tp]] = x;
    }
    return x;
  };

  vector<leftnode*> mcm_solution(N);
  const auto mcm = [&ufds, &fnd, &mcm_solution](const vector<leftnode*>& l, int r) {
    fill(mcm_solution.begin(), mcm_solution.begin() + r, nullptr);
    iota(ufds.begin(), ufds.begin() + r + 1, 0);
    for (auto ptr: l) {
      int x = fnd(ptr->l);
      if (x <= ptr->r) {
        mcm_solution[x] = ptr;
        ufds[x] = x + 1;
      }
    }
  };

  vector<unsigned char> label(sz);
  vector<int> proj[2][2]{vector<int>(N), vector<int>(N), vector<int>(N), vector<int>(N)};
  const auto mwm = [&mcm, &mcm_solution, &label, &ufds, &fnd, &proj, data_ptr]
      (const auto& self, const vector<leftnode*>& l, int u, int r) -> int {
    if (l.empty() || r == 0) return 0;
    auto cmp = [] (const leftnode* a, const leftnode* b) {
      return a->val > b->val || (a->val == b->val && greater{}(a, b));
    };
    if (u <= 1) {
      int tot = 0;
      for (auto ptr: l) tot += ptr->val;
      if (u == 0 || (mcm(l, r), count_if(mcm_solution.begin(), mcm_solution.begin() + r, identity{}) == (ptrdiff_t)l.size())) {
        return tot;
      } else {
        return tot - (*max_element(l.begin(), l.end(), cmp))->val;
      }
    }
    int uu = u / 2;
    vector<leftnode*> ll(l);
    nth_element(ll.begin(), ll.end() - u, ll.end(), cmp);
    auto val2 = ll.end()[-u];
    nth_element(ll.end() - u, ll.end() - uu, ll.end(), cmp);
    auto val = ll.end()[-uu];
    copy_if(l.begin(), l.end(), ll.begin(), bind(cmp, placeholders::_1, val));
    ll.resize(ll.size() - uu);
    mcm(ll, r);
    vector<leftnode*> even;
    even.reserve(ll.size());
    for (auto ptr: l) {
      label[ptr - data_ptr] = false;
    }
    for (auto ptr: ll) {
      label[ptr - data_ptr] = true;
    }
    for (int i = 0; i < r; i++) {
      if (mcm_solution[i]) label[mcm_solution[i] - data_ptr] = false;
    }
    for (auto ptr: ll) {
      if (label[ptr - data_ptr]) {
        even.push_back(ptr);
      }
    }
    iota(ufds.begin(), ufds.begin() + r + 1, 0);
    while (!even.empty()) {
      const auto ptr = even.back();
      even.pop_back();
      label[ptr - data_ptr] = true;
      for (int x = fnd(ptr->l); x <= ptr->r; ufds[x] = x + 1, x = fnd(x + 1)) {
        if (label[mcm_solution[x] - data_ptr]) continue;
        label[mcm_solution[x] - data_ptr] = true;
        even.push_back(mcm_solution[x]);
      }
    }
    vector<int> iii[2];
    for (int i = 0; i < r; i++) {
      bool ok = mcm_solution[i] && label[mcm_solution[i] - data_ptr];
      iii[ok].push_back(i);
    }
    vector<leftnode*> nxtl[2];
    for (int t = 0; t <= 1; t++) {
      auto it = iii[t].begin();
      for (int i = 0; i < r; i++) {
        while (it != iii[t].end() && i > *it) ++it;
        proj[t][0][i] = (it == iii[t].end() ? 1'000'000'000 : it - iii[t].begin());
      }
      auto it2 = iii[t].rbegin();
      for (int i = r - 1; i >= 0; i--) {
        while (it2 != iii[t].rend() && i < *it2) ++it2;
        proj[t][1][i] = (it2 == iii[t].rend() ? -1 : it2.base() - iii[t].begin() - 1);
      }
    }
    int l0 = 0, l1 = 0;
    for (auto ptr: l) {
      if (label[ptr - data_ptr]) {
        ptr->l = proj[1][0][ptr->l];
        ptr->r = proj[1][1][ptr->r];
        if (ptr->l <= ptr->r) {
          nxtl[1].push_back(ptr);
          l1 += !cmp(ptr, val2);
        }
      } else {
        ptr->l = proj[0][0][ptr->l];
        ptr->r = proj[0][1][ptr->r];
        if (ptr->l <= ptr->r) {
          nxtl[0].push_back(ptr);
          l0 += !cmp(ptr, val);
        }
      }
    }
    return self(self, nxtl[0], l0, iii[0].size()) + self(self, nxtl[1], l1, iii[1].size());
  };
  return mwm(mwm, l, sz, N);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<leftnode> l(n);
  for (auto& t: l) {
    cin >> t.l >> t.r >> t.val;
    t.l -= 1;
    t.r -= 2;
  }
  vector<leftnode*> ll(n);
  iota(ll.begin(), ll.end(), l.data());
  sort(ll.begin(), ll.end(), [] (const leftnode* a, const leftnode* b) { return a->r < b->r; });
  int N = ll.back()->r + 1;
  int ans = solve(ll, N, l.data());
  cout << ans << endl;
}

:::

参考资料

1. Spencer, T.H., and Mayr, E.W. (1984). Node weighted matching. In: Paredaens, J. (eds) Automata, Languages and Programming. ICALP 1984. Lecture Notes in Computer Science, vol 172. Springer, Berlin, Heidelberg.
2. Lovász, László, and Plummer, Michael D. (2009). Matching Theory. AMS Chelsea Publishing.
3. 柯绎思，《顶点带权的图匹配问题》，IOI2024 中国国家集训队论文。