<分区>
给定一个有 n 个顶点的无向图，我们需要选择一些边 [比如边数 = m { m>=1 和 m<=floor(n/2)} ] 以使它们不共享任何公共(public)顶点和所有选定边的权重之和被最大化。 我们需要找到所有选定边数(1 到 n/2)的最大总和。
<分区>
给定一个有 n 个顶点的无向图，我们需要选择一些边 [比如边数 = m { m>=1 和 m<=floor(n/2)} ] 以使它们不共享任何公共(public)顶点和所有选定边的权重之和被最大化。 我们需要找到所有选定边数(1 到 n/2)的最大总和。
最佳答案
这个问题已经有了多项式时间算法。
如果图是二分图，网络流和匈牙利算法可以做到。
否则，开花算法可以在一般图上构造最大匹配。
关于c++ - 满足以下条件的高效图算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58776147/