【题解】洛谷P6857 梦中梦与不再有梦

题目

洛谷P6857梦中梦与不再有梦

题解

前置知识:给定一张无向图,若存在一条路径,恰好经过每条边一次(即俗称的一笔画),则称该路径为欧拉路径。若欧拉路的起点和终点相同,则称其为欧拉回路。

存在欧拉回路的充要条件:(无向图)所有点度数为偶数;(有向图)所有点的入度和出度相等。

存在欧拉路径(但不是欧拉回路)的充要条件:(无向图)除两点外,其余点的度数为偶数,且度数为奇数的两点为起点和终点;(有向图)起点出度比入度大1,终点入度比出度大1,其余点入度等于出度。

本题要求一笔画的最长路径,即选出一部分边,构造欧拉路径,且要求路径最长。即删去最少的边,使图中存在欧拉路径。题目中的图是强联通图,每个点的度数为(n-1)。若n为奇数,则度数为偶,存在欧拉回路,若n为偶数,则要将(n-2)个点的度数-1。注意:删去一条边,相当于将两个点的度数-1,即需要删去(n-2)/2条边。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年10月26日 下午7:19

【小白解析】
当n为奇数时,所有点度数(即联通该点路径之和)为偶数,可以保证到达该点的路径数量与从该点出发的路径数量一致,均为(n-1)/2,说明该情况下支持除了点i以外一半的点通向i,而点i可以通向剩下的一半点;故题目思路转化为求给定点数量,在任意两点之间画线,求线段总数量,即排列组合C(2,n)=n(n-2)/2:

if(n%2) printf(“%lld\n”,n*(n1)/2);

若n为偶数,要使路径数量最大且一笔画可行,需至少使n-2个点度数为偶数,剩余两个拥有奇数度数的点作为起点与终点:

删去一条边,相当于将两个点的度数-1,即需要删去(n-2)/2条边。

故最终路径总数为C(2,n)-(n-2)/2=n*n/2-n+1:

else printf(“%lld\n”,n*n/2n+1);

*Amazing John就暂且翻译作神熠