I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each and every home to one another. However, the tree is not the minimum spanning tree. You may use an enhancer, in exact words, with power D, to reduce the weight of one edge to what is max(0,weight-D). You have a number of days to make the given spanning tree a minimum spanning tree. During these days, you may deactivate any edge of the given spanning tree, and activate another edge of your choice. It does not matter if the tree is not a spanning tree in the process, however, at the end, it should be. You also want to minimize the amount of days you need to do this.
I have been struggling with the problem for a long time, and I cannot find any solution. I am able to find the minimum spanning tree, but I am struggling with the implementation of the enhancer.
I would appreciate any help to my problem, and sample codes will be even better.
I asked a similar question here as well: Minimum spanning tree such that one edge can be minimised