[题目大意]给出一个无向完全图,图中的边都被染成了某种颜色[1,M],求一个颜色集合,使得包含了这些边以后,图中的任意两点的最短路<=3
可以证明将前(M+1)/2颜色分成一组,其余的颜色分成一组以后,必有一组符合条件.
如果A集合符合题目要求,则命题成立,否则假设A集合不符合题目要求,也就是存在两个点ab,他们的距离大于3,或者两者无法互相到达.
下面考虑B集合.
对于任意点对(xy),如果 A,必有∈B,所以在B中的距离<=3.
对于任意点对(xy),∈A,如果a在A中不和xy中的任意一个有直接连边,则在B中存在;如果b在A中不和xy中的任意一个有直接连边,则在B中存在.因此可以假设a b在A中都和x或y有直接联系.
这样在A中就存在或类似的路径,长度不超过3.这和我们的假设前提"ab在A中的距离超过3或者不连通"矛盾. 因此不可能存在ab在A中都和x y有直接联系这种情况.
所以不论∈A还是 A,他们在B中的距离都不超过3.所以,如果A不满足题目要求,B必然满足要求.