首页 > 其他 > 详细

星际旅行

时间:2019-07-18 22:39:03      阅读:77      评论:0      收藏:0      [点我收藏+]

0分

瞬间爆炸。

考试的时候觉得这个题怎么这么难,

打个dp,可以被儿子贡献,可以被父亲贡献,还有自环,叶子节点连边可以贡献,非叶子也可以贡献,自环可以跑一回,自环可以跑两回,

关键是同一子树会贡献,不同子树也会贡献。

这还不是欧拉图欧拉路问题,awsl

然后我就放弃了这个题

考完试看题解,tm一个大水题

虽然好像不算水,

思考两个点之间因为连接的是无向边,所以所有点入度出度都为2。

先不考虑自环

如果把两个点之间无向边拆成两个有向边,那么问题就变成去掉两个边使原图存在欧拉路。

于是乎,问题就变得很简单了

如果有自环

可以去掉两个自环,或者去掉一个自环和一个边

 

星际旅行

原文:https://www.cnblogs.com/znsbc-13/p/11209930.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!