BUZZ - To inifinity and Beyond
You probably don't know toys walk, play and talk when we are not around. And there are toys who can perform intergalactic missions! But lets forget about alien planets now, the toy-land on earth is in danger, “Zurg” the evil emperor from outer world is planning to capture it. But as always when toyland is in trouble the great space ranger “Buzz Lightyear” of star command comes for the rescue!
Toyland consists of several cities and bidirectional roads. The Toyland chief wants to take following steps to save Toyland:
- First divide the cities of Toyland into multiple regions. Two cities MUST be included in same region if there is at least one cyclic route connecting both cities. One city can be included in multiple regions. Size of each region should be maximal, that means extra city can't be added in a region.
- There are limited number of “Buzz” toys available. After creating the regions, one “Buzz” toy will be sent to each of them to save that region from Zurg!
Toys need energy. Each city can supply energy to infinite number of toys but the amount of energy a city provides daily to a single toy is limited otherwise toys may waste energy. A toy is assigned to a single region but it can get energy from any city with in its region.
For a single toy, the total daily energy supply is sum of the energy supply of all the cities within its region.
Each “Buzz” may need different amount of energy to work. If a region provides too little energy than additional energy need to be provided anyhow and it is considered as a loss. But if the region provides more energy than required, “Buzz” wastes it by playing with laser and flying all around. So:
Daily Loss in region X =
| Daily Energy required by “Buzz” assigned in that region - Daily Energy supplied by region X |
Exactly one “Buzz” must be assigned in each region, if there are more toy than needed, they'll keep them for emergency. The chief wants to minimize the maximum wastage among all the regions and he needs your help desperately.
Help the toyland to survive, expand your mind To Infinity and Beyond and find the answer.
Input
Input consists of several files. First line of each file will consist the number of test cases (T <= 101). For each case, first line will consists number of cities (1 <= N <= 251), roads (E >= 0) and number of Buzz toys available (1 <= B <= 251). In next line there are N integers less than 1000, i-th integer denotes energy supply in city i. In next line there are B integers less than 1000, j th integer denotes energy required by Buzz j. Next there are E lines each consisting two integer u and v denoting there is a bidirectional road between u and v (u != v). There are at most one roads between two cities. All inputs are non-negative.
Output
First print number of regions. Than if number of regions is more than number of buzz available, output “No”. Otherwise print the maximum wastage amount among all the regions. Dont print any extra spaces or newlines. Print case number for every case, see sample output for details.
Sample
Input: 2 6 7 3 5 4 8 1 2 6 10 14 9 1 2 2 3 3 1 3 4 4 5 3 5 5 6 4 3 1 5 4 8 1 10 1 2 2 3 3 1 Output: Buzz Mission 1: 3 3 Buzz Mission 2: 2 No
Large input File, use faster I/O.
hide comments
searleser97:
2021-01-16 04:26:18
Biconnected Components + small DP at the end
|
|
mabdallah:
2015-11-27 13:32:24
you can solve it by using greedy algorithm, semi easy Last edit: 2015-11-27 13:32:53 |
|
TINYJR:
2012-12-25 06:53:59
Could someone tell me the algorithm to solve this problem?? |
Added by: | Shafaet |
Date: | 2012-12-11 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own problem (9th IIUC Inter-University Programming Contest, Bangladesh) |