欧拉路径
代码
细节较多
link
欧拉回路
中国邮递员问题
求从点\(s\)出发，遍历所有边，最后回到\(s\)的最短路线
考虑回路的性质：每个点的度都为偶数
那么只需要求将奇度点两两配对的最小代价即可
（算法？
P6628 [省选联考 2020 B 卷] 丁香之路
把起点和终点连一条边，则转化为上面这个问题
观察图的性质，边权为\(|i-j|\)，则图可对应在一个数轴上
此时相当于在序列上考虑奇点匹配，发现贪心地将\(i_1\)和\(i_2\)匹配，\(i_3\)和\(i_4\)匹配即可
但是这样匹配会使图不连通，对每个连通块连边求最小生成树即可
疑问：为什么这样做是对的，会不会有一种较劣的匹配方案但是可以使图联通，使得总代价更小呢
旅游
小结
发现上面的模型都是：找一条回路，使得给定\(m\)条边至少经过\(1\)次
至于为什么丁香之路不用欧拉路径，因为回路有偶点的性质，更好处理