首先提出结论:此题进行最小生成树之后结果不变 靠着这个结论,我们显然可以在最小生成树上以 为根遍历,处理出到每个节点的最大边权,进而求出到每一种类型的节点最小的最大边权。题意要求我们求从 到 中每一种最大边权可获得的类型总数,由于节点种类数较少,考虑对于每个节点最小所需的边权排序,然后按照每一种最大边权可以获得的节点分类,统计最后答案。 接着证明上述结论。考虑 Kruskal 算法中的贪心思想,假设前 条边都已考虑完毕,设第 条边连接 和 两个集合(树),则当前如果有另外的边能够连接此二集合,肯定会边权更大,在 和 两个集合统计答案时答案不会更优。再者两个集合内已经被...