I am thinking of finding all the possible MSTs and maintaining the set of edges that were not considered in each MST, and then get the minimum cost from that set.
Is it the correct logic?
any other approach to the question?
Cyber attack Problem
Hello @shivanshu12800
This question can be solved greedily by finding Maximum Spanning Tree, MST(which can be found using minimum spanning tree algorithms). For the graph to remain connected, leave the edges of the MST. Now sort the remaining edges in the increasing order of their cost, remove the edges until the sum of costs of removed edges doesn’t exceed the allowed total cost.
Here for yorur reference i am attaching the code:
if you have any doubt you can ask here:
Happy Learning!!
https://ide.codingblocks.com/s/393592 Bro the code gives wrong answer, please check my code. I implemented the MST algorithm taught by bhaiya with the negative weights and then inserted the weight of the edges not included in the MST into set, and then simply ran the for each loop
@shivanshu12800 it is because your logic is also varies.
the code which i have given to you is passing all the test cases.
you can see that code.
if you dont understand anything you can ask here:
Happy Learning!!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.