POJ 1637 - Sightseeing Tour
Problem : Check the mixed graph if it has euler loop.
Solution :
1. If a vertex has odd degree, return false.
2. Set the bidirectional edge to arbitrary orientation, and has the capacity 1.
(After set bidirectional edge to directional edge)
3. For each vertex, if its out degree > in degree, set an edge from source vertex to it, has capacity (out degree - in degree)/2. If its in degree > out degree, set an edge from vertex to sink, has capacity (in degree - out degree)/2.
4. If total capacity from source = total capacity to sink, and the maximum flow can full it, return true. Otherwise false.
Proof : It's very complex to prove the algorithm, the detail is at the note in maximum flow series.