< Back to forum

E - Destruction

Problem Statement

Graph

Asked by: Anonymous on Sept. 24, 2021, 4:05 p.m. Last updated on Sept. 24, 2021, 4:05 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

The problem is based on the concept of minimum spanning tree and specifically on Kruskal's algorithm.

The key point to notice here is that after removal of edges, the total cost of edges in the remaining tree is minimum possible. That gives us and idea of the concept of minimum spanning tree.
So, we can sort the edge weights in ascending order and use Kruskal's algorithm to complete the tree. The only edge case here is that there are negative weights also, so you should pick negative weights as well even if they are not a part of the minimum spanning tree.

mahawarvishal10 last updated on Sept. 24, 2021, 10:54 p.m. 2    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.