请教大家关于 中国邮递员 问题

镕羽

我觉得下面第四步中 求完备匹配 有点问题。
' ^& e+ r- x6 B  z$ K  B; E
$ G' O) t. F% H4 H5 Y
, m7 C9 V0 i: w( o8 U
4 A' D; Y# z# \) k  y
5 N% g7 v/ P+ W# c0 Q. F上面的图4情况 求出{v1v4，v2v3}组合没错；
' n5 |. `% z' K5 _但是如果是这样的情况，按照完备匹配法来求就不对了：
% }4 i1 R" l* f* u
就是有可能  v1v3间距离很短（如只有1），v1v2间距离也很短（如只有1）
% N- r) E* x/ s. V2 _4 B, r+ H
" K7 P- Q9 X0 q  k8 B0 {0 ?5 }; V那选择“倍边”时，就选{v1v4，v1v2，v1v3}，所有奇数度点 都成了偶数，再来找欧拉回路。
（这种情况不能用完备匹配法求解）
) V5 }: s! e6 U
所以就觉得 用完备匹配 找 倍边的 方法不能涵盖所有情况，有点问题。

镕羽

请教大家 哪里想错了？

guoxbcqupt

编程试试，看看结果怎么样·····

御剑逍遥

最短路11步     有关知识参考最短路问题

御剑逍遥

由v3  u4  v2   u3   u2   v1   u1   v4   u6         再由u2到v5   加和11   不知对不？
% g0 r4 e, X3 ]; a