求满足无向图多阶最大权匹配条件的高效图算法

首先，咱们明确问题核心：你需要对每个m（从1到⌊n/2⌋），在无向图中选出m条无公共顶点的边，使得它们的权重总和最大。这个问题本质是带规模约束的最大权匹配问题，普通的最大匹配算法只能给出单一规模的最优解，咱们需要一种能批量计算所有规模最优值的高效方法。

最优解法：基于最大费用流的增量计算 #

最通用且高效的思路是把问题转化为最大费用流（或最小费用流）问题，通过增量式增广来获取每个m对应的结果，步骤如下：

1. 构建流网络模型 #

我们需要把原图的顶点拆分来避免顶点被重复选中：

• 将每个原图顶点u拆成两个节点：u_in（入点）和u_out（出点）。
• 新增一个源点S和汇点T：
  • 从S向每个u_in连一条容量为1、权重为0的边（限制每个顶点只能被选一次）。
  • 从每个u_out向T连一条容量为1、权重为0的边。
• 对原图中的每条无向边(u, v)（权重为w），添加两条有向边：
  • 从u_out到v_in，容量1，权重w；
  • 从v_out到u_in，容量1，权重w。
    这样就把原图的边转化为流网络中可选择的“匹配路径”。

2. 增量计算每个m的最大权和 #

我们通过多次寻找最大权增广路，逐步累积流量，就能得到每个规模m的结果：

• 初始化总权重和为0，当前已选边数（流量）为0。
• 循环直到达到⌊n/2⌋条边或找不到增广路：
  1. 在当前流网络中找最大权增广路（从S到T的路径，剩余容量>0，且路径总权重最大）。
  2. 如果找不到增广路，说明无法再选更多边，直接终止。
  3. 将这条增广路的权重加到总权重和中，记录当前流量m = 当前流量+1对应的总权重值。
  4. 更新流网络的剩余容量：增广路上的边容量减1，反向边容量加1（这是费用流算法的标准操作）。

3. 算法效率说明 #

• 每次找最大权增广路可以用Dijkstra算法（配合势函数处理可能的负权反向边，确保效率），时间复杂度为O(M + N log N)，其中N是流网络的顶点数（2n + 2），M是流网络的边数（2n + 2m）。
• 最多进行⌊n/2⌋次增广，总时间复杂度为O(⌊n/2⌋*(M + N log N))，这在大多数实际场景中都是高效的，尤其是当n和m不是极端大的时候。

为什么不用贪心？ #

很多人会想到先选最大权重的边，再选次大且不冲突的，但这种贪心策略只对m=1有效。比如：假设存在两条权重为5的边共享一个顶点，还有两条权重为4的边无冲突，当m=2时，贪心选一条5的边后只能放弃，总和为5，但最优解是选两条4的边总和8。所以贪心无法得到所有m的最优解。

内容的提问来源于stack exchange，提问作者pranshu garg