带指定权重图的最大MST求解：完全图Kₙ权重分布问题

嘿，你的这个想法有两个关键的小错误哦，咱们一步步来理清楚：

首先，最小生成树（MST）是连接所有n个顶点的树结构，树的边数固定是顶点数减一，也就是n-1条，不是n条——这是第一个要纠正的点。其次，我们的目标是找到MST的最大可能权重，这意味着要尽量少用权重为1的边（毕竟1比2小，用得越少总权重越大），而要做到这一点，核心是让权重为1的边构成的子图拥有尽可能多的连通分支。

接下来咱们详细分析：

核心逻辑：连通分支数决定MST权重 #

假设权重为1的边构成的子图有c个连通分支，那么MST要把这c个分支连起来，就需要用c-1条权重为2的边（因为没有权重1的边连接不同分支），剩下的(n-1)-(c-1)=n-c条边则是从每个连通分支里选的权重1的边（每个连通分支是一个图，我们可以在里面选一棵树的边，都是权重1）。

所以MST的总权重就是：
(n - c)*1 + (c - 1)*2 = n + c - 2
要让这个值最大，我们只需要最大化c——也就是让权重1的边构成的子图的连通分支数尽可能多。

最大化连通分支数c的条件 #

我们有n个顶点、n条权重1的边，要构成连通分支最多的简单图（因为是完全图的子图，没有重边）：

• 每个连通分支至少要是一个单圈图（边数=顶点数，也就是树加一条边，刚好有一个圈），因为如果是树的话，边数=顶点数-1，会占用更少的边，没法凑够n条边。
• 单圈图最少需要3个顶点（三角形），所以我们可以把顶点分成尽可能多的3顶点组，每组构成一个三角形（3条权重1的边）：
  1. 当n是3的倍数（n=3k）：分成k个不相交的三角形，每个三角形的3条边设为权重1，此时c=k=n/3，总权重为n + n/3 - 2 = (4n)/3 - 2。
  2. 当n=3k+1：分成k-1个三角形，剩下4个顶点构成一个4顶点的圈（4条权重1的边），此时c=k=(n-1)/3，总权重为n + (n-1)/3 - 2 = (4n - 7)/3。
  3. 当n=3k+2：分成k-1个三角形，剩下5个顶点构成一个5顶点的圈（5条权重1的边），此时c=k=(n-2)/3，总权重为n + (n-2)/3 - 2 = 4(n-2)/3。

达到最大权重的权重分布 #

要实现这个最大权重，只需要按上面的方式分配权重1的边：

• n=3k：把顶点均匀分成k组，每组3个顶点，每组内的3条边设为权重1，其余所有边设为权重2。
• n=3k+1：k-1组3顶点三角形（组内边权重1），剩下4个顶点之间的4条圈边设为权重1，其余边权重2。
• n=3k+2：k-1组3顶点三角形（组内边权重1），剩下5个顶点之间的5条圈边设为权重1，其余边权重2。

举个例子：比如n=6（3*2），分成两个三角形，每个三角形的3条边是1，其余边是2。MST需要连接这两个三角形，所以用1条权重2的边，加上每个三角形里选2条权重1的边，总权重是2*2 + 1*2 = 6，刚好符合(4*6)/3 -2=8-2=6，这比全用权重1的边（总权重5）要大，完美体现了最大权重的情况。

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