UVA 10735 混合图的欧拉回路判断以及输出路径（最大流）

我不是女神ヾ 2022-10-02 12:55 90阅读 0赞

## 题意： 给出一个V个点E条边的混合图（有的是有向边，有的是无向边）求出它的一条欧拉回路，如果没有输出无解信息，输入保证忽略边的方向后图是连通的（V<=100, E<=500）。   分析： 按照往常的思维，遇到混合图，我们一般会把无向边拆成两条方向相反的有向边。但是在这里却行不通了，因为拆成两条有向边的话，就表示这个边能“在两个相反方向各经过一次”。而题意是这个边只能经过一次。 ##

## 复习欧拉回路：入度==出度，先给无向边定向。原图为G，定向的边单独组成另一个G’，定向后对任意点，入度==出度，则有了回路。否则调整原来的无向边。  （如果入度出度奇偶性不同，则无解），出度增加（in-out/2）。注意U->V变成V->U，U出度-1，V出度+1. 就像在运送”出度”，就是网络流。（满足out>in的点能提供出度） （可以提供的出度为diff\[i\]/2，需要接受的出度为-diff\[i\]/2），原有的边cap为1（只能改一次方向），设立超级节点S，T，S连可以提供的节点，cap为可以提供的出度，T类似。当sum可以提供的出度!=MaxFlow，就无解。否则有解（必须提供出去。这里可以证明提供出去后所有的点in==out）。求欧拉回路路径，这个用fluery算法即可。建图如下。 ##

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]   总结：   代码：待补。参考[https://www.cnblogs.com/lqerio/p/9860934.html][https_www.cnblogs.com_lqerio_p_9860934.html]。 ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: /images/20220112/f2b75a02ba3044049545c396edff5b4c.png
[https_www.cnblogs.com_lqerio_p_9860934.html]: https://www.cnblogs.com/lqerio/p/9860934.html