hdu6311如何求解无向图的最小路径覆盖问题？

本文共计1866个文字，预计阅读时间需要8分钟。

这道题目主要讨论的是一个算法问题。其核心是求解无向图的最小路径覆盖。简单来说，就是找到一种方式，用最少的边来覆盖图中的所有顶点。

与有向图的不同之处在于，对于有向图的最小路径覆盖，我们将其转化为求解最小欧拉路径。而在这里，我们直接求解无向图的最小路径覆盖。

欧拉图的一个结论是：如果一个图的每一条边都恰好属于一条欧拉路径，那么这个图就是一个欧拉图。在欧拉图中，欧拉路径的数量为2（如果图有偶数条边，则为偶数个欧拉路径，否则为奇数个）。因此，求解最小路径覆盖问题可以转化为寻找这些欧拉路径，并计算它们覆盖的边数。

欧拉路径的度数（即路径上的顶点数）可以用来计算最小路径覆盖的边数。欧拉路径的度数为路径上的顶点数，除以2（如果路径为偶数长，则为奇数长），得到的值就是路径覆盖的边数。因为每个顶点被计算了两次（一次进入，一次离开），所以最终结果是这个值的一半。

综上所述，这个算法的关键在于寻找图中的欧拉路径，并计算它们的覆盖边数，以实现最小路径覆盖。

这题主要是个套路。。就是求无向图最小路径覆盖。。

与有向图的二分图做法不同，这个是转化为求最少的欧拉路径。。

欧拉图有个结论是欧拉路径的个数为度为奇数的点的个数/2（可以类比欧拉回路的结论）

然后求欧拉路径的方法是fleury算法。。其思想就是暴力dfs，然后巧妙的地方就是边是方向取的，即以出栈的顺序为欧拉路径。。

然后就是一大堆细节问题。。大概是今天没什么人做出来的原因。。。

这题其实覆盖得情况比较全面（偶数的欧拉回路，奇数的欧拉回路和欧拉路径、分块求欧拉路径等），作为模板其实挺合适。。可以记下来。。