[POJ 2404] 中国邮递员问题、一般图最小权匹配、欧拉回路

【题目大意】给定一个无向图,让你求从其中一个点出发,经过所有边,回到这个点(边可以重复走)的最短总长度。

【算法分析】

如果是直接给欧拉图的话,就是输出边权和就可以了。

否则的话,就先floyed,然后求出任意两点的最短路。

然后给每对度为奇数的点连边,然后就是求一般无向图的最小权匹配了。

这个有经典算法的,叫带花树,不过我不会

所以,只能用状态压缩动态规划水过。

【其它】暴力47MS。。。

【程序】

#include

加入对话

6条评论

留下评论

您的电子邮箱地址不会被公开。