UVa 117

From Algorithmist
Jump to navigation Jump to search

117 - The Postal Worker Rings Once[edit]

Summary[edit]

This problem reduces to a Graph, by looking at each first or last character as a vertex, and the street name as an edge. We can reduce this problem to a Eulerian Path or a Eulerian Cycle problem, since each vertex will have an even number of degrees (except for at most 2 vertices).

Explanation[edit]

Even though at first glance, it seems like it might need the Chinese Postman algorithm, but since each vertex will have an even number of degrees (except for at most 2 vertices), we can use the simplier Eulerian Path/Eulerian Cycle algorithm instead. If all vertices are of even degrees, then you're done, since the solution is simply the Eulerian Cycle - the sum of the weights of all the edges. Otherwise, we will have to calculate the Eulerian Path, then you will have to find the shortest path between the two odd-degree vertices. This can be done with any of the Shortest Path algorithms.

Input[edit]

one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend

Output[edit]

11
114

Solutions[edit]