Million Dollar Vicky
Vicky wishes to be the richest ice cream parlor owner of Varanasi. For this he must install ice cream parlors on the roads such that every road has at least one such parlor. Vicky has figured out that the obvious optimal strategy would be to install them on the junctions of roads so that more than one road gets covered by a single ice cream parlor (A junction, as considered here, can also be the end point of a single road such that installing an ice cream parlor there will cover just that single road). Vicky wishes to install exactly k Ice cream parlors and yet cover every road in Varanasi. Help Vicky figure out whether it is possible to cover every road in Varanasi by installing exactly k ice cream parlors.
Note: Don’t waste your time finding a polynomial time algorithm for the problem as none are known to exist for this question till now. Instead use smart optimization to achieve a good enough solution as the test cases have been designed in a way that a good heuristic should do the needful well within time.
The first line contains the number of test-cases T, followed by a blank line, followed by T test cases each separated from the previous one by a blank line. The first line of each test-case contains three space separated integers – n - Number of road junctions in Varanasi, e – Number of roads in Varanasi and k – Number of ice cream parlor Vicky wishes to install.
Thereafter follows e lines, each containing two integers xi and yi which are the road junctions connected by the ith road.
There is no road which connects a junction to itself, nor are there multiple roads connecting the same pair of road junctions.
For each test case output a “YES” in case such an arrangement is possible, otherwise “NO”, on a separate line. (without quotes)
T <=6 1<= n <=100 1<= e <= n(n-1)/2 1<= k <= n
Input: 1 3 3 2 0 1 1 2 2 0 Output: YES
Selecting any two cities will help cover all the roads.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, GO|
Fetching successful submissions