hdu 1956(混合图的欧拉回路)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1956

思路:先将无向边定向,比如1<->3,可以定它的方向为1->3,1的出度++,3的入度++即可。读入的时候如果遇到无向边,把这条边加入待建的网络中,流量为1。读入完后,然后用出度减入度得到x,如果x为奇数,肯定不存在欧拉回路,如果没有奇数,就用最大流求解。 如果x大于0,则建一条s(源点)到当前点容量为x/2的边,如果x小于0,建一条从当前点到 t(汇点)容量为|x/2|的边。然后求最大流,如果是满流(即s出的流==t入的流即可,s指的是建图的时候连接s的边的容量和)就满足欧拉回路。

http://paste.ubuntu.com/5991463/

原文地址:https://www.cnblogs.com/wally/p/3261826.html