# Minimum Spanning Tree with one particular edge minimised(continued)

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

• @Apass.Jack This was the exact problem I was hoping to solve. Sorry for my bad phrasing of the question. – Aarony Jamesys Feb 16 '19 at 14:47
• @j_random_hacker the spanning tree OP mentioned is the current valid plan given in the problem. – John L. Feb 16 '19 at 18:14

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights, with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe.

At end of the algorithm, we obtain a minimum spanning tree $$T$$ with weights $$w_1\le\cdots w_{N-2}\le w_{N-1}=m$$. The number of days needed to implement $$T$$ as the new active pipes, denoted $$p$$, is the number of pipes in $$T$$ that are not currently active.

With the enhancer used, the total minimal cost becomes $$w_1+w_2+\cdots+w_{N-2}+s(w_{N-1})$$, where $$s$$ is the function such that $$s(w)=0$$ for $$w\le D$$ and $$s(w)=w-D$$ otherwise. That formula is shown in the linked question and its answers.

Can we reduce the number of days from $$p$$ to $$p-1$$?

Claim 1. If $$D\le m$$, then the number of days cannot be reduced to $$p-1$$.

The proof of claim is left to readers as a (not immediate) exercise.

So let us run Kruskal's algorithm again from scratch, with a further modification. Immediately after we have tried selecting all pipes of cost $$m$$ that were active (there might be none of them), we will continue to try selecting all pipes that cost more than $$m$$ but no more than $$D$$ one by one. If it is successful at least once, that is, if such a pipe will connect two disconnected components, then we will include it in the plan and we will reduce the required days by one to $$p-1$$. Otherwise, the required days is $$p$$.

• Would you mind providing me with some sample/pseudo code? – Aarony Jamesys Feb 17 '19 at 3:50
• What if the MST were not unique? Then, wouldn't the claim of "The number of days needed to implement T as the new active pipes, denoted p, is the number of pipes in T that are not currently active." be incorrect? – Aarony Jamesys Feb 17 '19 at 13:46
• In that case, wouldn't we need to find all cases of MSTs and find the minimum of value p? – Aarony Jamesys Feb 17 '19 at 13:49
• All MSTs are sort of equivalent to each other. Even if we obtain different MSTs, $p$ will be the same. Yes, MSTs are very remarkable. – John L. Feb 17 '19 at 13:51
• I have a test case which has all edge weights identical to each other. Clearly, finding an MST is somewhat pointless, yet given an MST, it may return a nonzero integer p. However, that would be incorrect. – Aarony Jamesys Feb 17 '19 at 13:55