问题重述（原题简化得来）：
给定一个简单联通无向图，包含n个顶点，每条边有一个正整数边权。定义两顶点距离为两顶点间路径最大边权的最小值。记k个顶点为特殊顶点，记f(i)为i顶点分别到k个顶点的k个距离中的最小距离，记score=f(1)+f(2)+...+f(n)。现在需要最小化score。则以下贪心算法是正确的：先找一个特殊顶点最小化score，然后在此基础上贪心地选下一个特殊顶点……直到选出k个特殊顶点为止，则这k个特殊顶点是最优的。
证明过程：
对于该图，按照Kruskal算法求最小生成树的流程建reachability tree。在reachability tree上，假设我们有最优解S，|S|=k+1，以及最优解T，|T|=k。则我们总是可以构造一种过程，把S里面的其中k个顶点替换成T的k个顶点。
大致原理是：因为我们获得T这个最优解的贪心过程中有一系列最优解F(1)，F(2)，...，F(k)，|F(i)|=i，并且显然集合差F(i+1)-F(i)恰好包含一个元素（一个叶节点），记这个元素为x。所以原来的问题就可以简化为：如果现在S里面的其中i个顶点已经能够替换成F(i)里的i个顶点，那么总是可以在S里面再找一个顶点，使得其可以替换成x。
如何找这个顶点？记S'=S-F(i)，则从x不断向父节点行走，直到走到某个非叶顶点v，使得以v为根的子树的两个直接子树，一个包含x而不包含S'的任何元素，一个包含S'的至少一个元素而不包含x。令这两个子树分别为G和H，不妨令G包含x，H包含S'的一部分，设S'的这部分为S''。我们又可以证明，∀e∈S''，都可以把e替换为x。证明如下：记S'''=S''-{e}。若将S'''暂时去掉，则将e替换成x显然是更优或等优的，因为v为根的子树里只有e或只有x的时候，e或x是该子树规模为1的最优解（该子树外部的顶点无法影响内部，这部分证明略过），当S'''存在的时候，e在H内对于答案的贡献只会更低或不变（这部分证明也略过），因此把e替换成x仍然是更优或等优的。
Q.E.D.
欢迎挑错
标签：977,包含,Codeforces,替换成,证明,Digital,顶点,最优,贪心 From： https://www.cnblogs.com/SeaYellow/p/18492313