Shichikuji and Power Grid

Source: Codeforces 1245D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
2. Identify the graph in the problem, and which famous graph problem is most similar to the problem we have to solve.
   • What distinguishes our problem from the famous problem?

It is not typical to combine vertex weights and edge weights.

3. Perform a construction to associate the cost of building a power station to an edge rather than a vertex.

4. Design an algorithm to solve the problem.

5. Analyse the time complexity of your algorithm and estimate its running time.

6. 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.
7. Submit your program for judging!
   • Debug as required.