BZOJ2887 : 旅行

如果小地图存在欧拉回路，那么对于大地图的每条边，都可以恰好走两次使得小地图每条边恰好经过一次，令$sum$为小地图的边权和，则此时答案为$m\times sum$。 否则小地图存在欧拉路径，找到两个奇点$A$和$B$，那么最优解中大地图每条边一定经过$1$次或者$2$次，且仅保留经过$1$次的边后大
posted @ 2020-01-07 17:30  Claris  阅读(304)  评论(0)  编辑  收藏  举报