MST company

骨质瓷>无缝钢轨Codeforces 125E MST Company

一个显而易见的性质：如果可以连入生成树的边越多，最小生成树的权值和一定不会上升。

督导论文

这个性质很容易让人想到二分，基于kruskal算法，我们可以很直接想到这样一个做法：

二分一个值W，每次判定时，不允许权值大于W的边连入生成树，判断最后连入最小生成树的有多少条边，这样连入的边数一定是递增的。

松崖别业图卷这个算法看似没有问题，但仔细思考就会发现，这并不是一个连续的值，可能正好跳过了我们要的度数的要求，而且也不一定能到最优解。

虽然这个算法是错误的，但这也是一个很好的思路，在这个基础上，进一步便可以想到正确做法：

二分一个实数W，每次判定时，让与1号点相连的边全部加上这个值。做最小生成树后，看与1相连的边有多少条在最小生成树中，显然随着W的增大，与1相连的边连入最小生成树的会越来越少，单调递减。

因为W是一个实数，因此最小生成树中点1的度数变化是连续的，一定可以得到度数要求，因此这个算法是正确的。南京321计划

江阴城南小学

本文发布于:2024-09-23 15:25:11，感谢您对本站的认可！

标签：连入生成算法度数权值看似

留言与评论（共有 0 条评论）