noip 模拟赛 星系旅行题解
一个利用欧拉回路的试题...根据题意要求,我们分析一下可以看出:一条边拆成两条边,那么原题等价于删去两条边后原图中仍然存在一条欧拉回路同时图中存在自环分析:①:删去一个自环和任意一条其他边②:删去两条非自环的边我们分别来讨论这两种情况,首先讨论一下②根据欧拉回路的性质以及题意,原图中所有点的度数一定是偶数,再考虑到没有重边,所以一条边连接的两点会分别获得2的度那么如...