Indian Computing Olympiad

Advanced Graph Algorithms→Roads (APIO 2008)

The Kingdom of New Asia contains N villages connected by M roads. Some roads are made of cobblestones, and others are made of concrete. Keeping roads free-of-charge needs a lot of money, and it seems impossible for the Kingdom to maintain every road. A new road maintaining plan is needed.

The King has decided that the Kingdom will keep as few free roads as possible, but every two distinct villages must be connected by one and only one path of free roads. Also, although concrete roads are more suitable for modern traffic, the King thinks walking on cobblestones is interesting. As a result, he decides that exactly K cobblestone roads will be kept free.

For example, suppose the villages and the roads in New Asia are as in Figure 1a. If the King wants to keep two cobblestone roads free, then the Kingdom can keep roads (1,2), (2,3), (3,4), and (3,5) free as in Figure 1b. This plan satisfies the King's criteria because (1) every two villages are connected via one and only one path of free roads, (2) there are as few free roads as possible, and (3) there are exactly two cobblestone roads: (2,3) and (3,4).

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

      

Solution

---