GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 18 May 2022

[Solution] Minimize Blocked Roads CodeChef Solution | CodeChef Problem Solution 2022

Given a network of N cities (numbered from 1 to N) and (N1) roads arranged in a tree format with the root at city 1.
Each of the (N1) roads is assigned a value of either 0 or 1.

  • If the value of a road is 0, it cannot be blocked by the government.
  • If the value of a road is 1, it may or may not be blocked depending on the decision of the government.
Solution Click Below:-  CLICK HERE

Initially, city numbered 1 is infected by a virus. The infection spreads from an infected to an uninfected city only if all the roads present on the shortest path between the cities are unblocked.

The government wants to control the number of infected cities and has asked you to devise a plan. Determine the minimum number of roads (with value 1) you need to block such that at most K cities are infected at the end.







If it is not possible that at most K cities are infected, print 1.

Input Format

  • The first line contains an integer T denoting the number of test cases. The T test cases then follow.
  • The first line of each test case contains two space-separated integers N and K, as given in the statement.
  • Each of the next (N1) lines consists of 3 space-separated integers UV, and X denoting that there exists a road between cities U and V with a value X (0 or 1).

Output Format

For each test case, output a single integer representing the minimum number of roads that need to be blocked such that at most K cities are infected at the end.
If it is not possible that at most K cities are infected, print 1.

Constraints

  • 1T1000
  • 1N2105
  • 1KN
  • 1U,VN and UV.
  • 0X1
  • Sum of N over all cases does not exceed 2105.

No comments:

Post a Comment