Electricity Solution KickStart(10pts, 15pts)
Problem
Ben works as an engineer in a city with electric junctions. These junctions form a network and can be visualised as a connected graph with vertices and edges. The city is facing a power outage, due to which none of the junctions are receiving electricity, and Ben is in charge of handling the situation.
Each junction has a fixed electric capacity. is the electric capacity of the -th junction. Due to resource constraints, Ben can provide electricity to only one junction, but other junctions can receive electricity depending on their connections and capacities. If the -th junction receives electricity, then it will also get transmitted to all the junctions directly connected to the -th junction whose capacity is strictly less than . Transmission stops if no eligible junction is present. Help Ben determine the maximum number of junctions that can receive electricity.
Input
The first line of the input gives the number of test cases, . test cases follow.
The first line of each test case contains an integer which represents the number of junctions in the city.
The next line contains integers. The -th integer is , which is the electric capacity of the -th junction.
The next lines each contain two integers and , meaning that the junctions and are directly connected to each other.
Output
For each test case, output one line containing Case #:
, where is the test case number (starting from 1) and is the maximum number of junctions that can receive electricity.
Limits
Time limit: 40 seconds.
Memory limit: 1 GB.
.
, for all .
, for all .
All the junctions are part of a single connected network.
Test Set 1
.
Test Set 2
For at most 15 cases:
.
For the remaining cases:
.
Sample
2 5 1 2 3 4 3 1 3 2 3 4 3 4 5 6 1 2 3 3 1 4 3 1 3 2 3 4 4 5 1 6
Case #1: 5 Case #2: 3
In Sample Case #1, the optimal solution is to provide electricity to the fourth junction. This will transmit electricity to all the junctions eventually.
If the electricity is provided to the third junction, it will transmit it to the first and second junction, but not to the fourth junction. In that case, only three junctions can finally receive electricity.
In Sample Case #2, the optimal solution is to provide electricity to the third junction. This will transmit it to the first and second junctions. Note that electricity will not be transmitted to the fourth junction, since its capacity is not strictly less than that of the third junction.
If electricity is provided to the sixth junction, it will only be transmitted to the first junction.
If electricity is provided to the fourth junction, it will only be transmitted to the fifth junction.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.