Road Construction

Source: ICPC Jakarta 2019

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
2. This graph has n vertices and n edges and is connected. Describe the structure of such a graph, and identify what subsets of roads could be built.

We know a lot about connected graphs with n − 1 edges. Let’s try to do the problem with this change in constraints.

3. If there were n − 1 edges instead, what would the structure of the graph be?
   • Explain why all the proposed roads have to be built.

4. Design an algorithm to allocate the K workers to the n − 1 roads, obeying the constraints on materials.

5. Analyse the time complexity of your algorithm and estimate its running time.
   • It should be too slow.
6. To improve your algorithm, notice that two workers who use the same material are effectively identical!
   • Adjust your flow network construction accordingly, and repeat the time complexity analysis.

Now, we can return to the original problem.

7. Recall from question 2 above that there are some roads that must be built, and others from which only some roads should be built.
   • Adjust your flow network construction accordingly, and if necessary repeat the time complexity analysis.
8. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
9. Submit your program for judging!
   • Debug as required.