洛谷10月月赛2T1题解

这道题就是给你一个完全图,问一笔画最多走几条边。
根据hzoi神犇老姚的博客,能被一笔画出来的联通图只能是一个欧拉图或是半欧拉图。
欧拉图:所有点度数均为偶数。
半欧拉图:除了两个点度数为奇数,其他点度数均为偶数。
我们考虑这道题。
如果(n)为奇数,那么每个点向其他点连边,每个点的度数都是(n-1),均为偶数,显然是一个欧拉图,所以一笔画最多经过的边数就是所有边(frac{(n-1)*n}{2})
如果(n)为偶数,那么每个点的度数都是奇数,显然这个图既不是欧拉图,也不是半欧拉图,那么一笔画出来的只能是它包含的最大欧拉图或半欧拉图。
首先考虑欧拉图,由于要求每个点度数都为偶数,所以对于每个点来说,都得删去与它相连的一条边,一共删去了(frac{n}{2})条边(每个点都删一条那每一条边就被删除了两次,要除以2)
然后是半欧拉图,由于还能保留两个点度数为奇数,所以比上面那种情况多加了一条边,使得某两个点度数+1,然后还满足一笔走完,一定更优。
所以当(n)为偶数,答案就是(frac{(n-2)*n}{2}+1)(每个点都有(n-2)个向外的连边,最后再在这个欧拉图上加一条边)

原文地址:https://www.cnblogs.com/liu-yi-tong/p/13836169.html