Indian Computing Olympiad

Training Material


Basic Graph Algorithms→Toll Roads (IOITC 2006)

As the well-known saying goes, all roads lead to Siruseri. The local government has decided to make all roads in the vicinity of Siruseri one-way and levy a toll on each of them. The orientation of the roads will be such that from any location there is at least one route to Siruseri. Moreover, the tolls will be assigned in such a way that the toll on every road is greater than zero and, from any location, the total toll paid to get to Siruseri is the same along any route. By route, the government means a consecutive sequence of roads such that the end point of each road is the starting point of the next one---a route may pass through the same road or city more than once.

For example, suppose the roads were originally as follows, where 1 denotes Siruseri.

             1
           /   \
          /     \
         2-------3
         |     / |
         |   /   |
         | /     |
         4-------5
      

We could orient the roads and assign tolls as follows:

             >1<
         1 /     \ 2
          |   1   |
          2<------3
          ^   --> ^
        2 |  | 1  | 2
          | /     |
          4<------5
              1
      

Here, for example, all paths from 5 to 1 have total toll 4.

Solution