algorithm - 最大可能分数

Question

我最近在招聘挑战中遇到了这个问题：

给定 N(1 <= N <= 10^5) 个节点和 M(3 <= M <= 10^5) 个边的有向图，每个节点的值表示从该节点可到达的节点数。图的得分是图中所有节点的值的总和。我们需要从中删除3 条边，以使图的得分最大并返回该最大值。

我的方法是找到一个循环并从中删除一个边缘。如果可能，重复相同的过程 3 次，否则移除叶子。但是我无法理解要从循环中删除哪个边缘或要删除哪个叶子，或者有任何其他方法。提前致谢。

标签： algorithmdata-structuresgraphdynamic-programming

Answer 1

假设图是完全连接的并且应保持在该状态：

1. 如果允许相同节点之间存在多条边，请先删除它们，因为您根本不会降低分数。

2. 删除指向同一节点的边。通过这样做，您将根据解释将该节点的分数降低 0/1。

3. 所有其他边都会将图形的总分降低 2（每个节点降低 1）。如果删除循环的边缘，则图形将保持连接状态。您删除循环的哪个边缘无关紧要。