EC_MODE - Modems
A Oruro province wants ALL the towns to have Internet access and to communicate with each other by at least one channel (not necessarily direct). The engineer in charge asks you to help him determine the minimum cost of providing this access.
There are N towns in total (1 <= N <= 1000). UTP can be used only up to range R (1<=R<=10000). If this distance is exceeded, optical fiber must be used instead. The unit cost of using UTP cable is U and the unit price of the optical fiber is V (U <= V; 1 <= U, V <= 10). There are also W satellite modems purchased (1 <= W < N). These satellite modems can be placed in any town. Satellite modem will allow a town to use the internet and communicate with any other modem in the province.
Input
The first line contains the number of test cases. First line of each test case consists of five integers N, R, W, U, V. Then N lines follow, each with integer pair xi, yi (-10000 <= xi, yi <= 10000), the coordinates of i-th town.
Output
For each case, print a line of the form:
Caso #TC: A B
Where TC is the test case number, A is the total cost of using UTP cable and B is the total cost of using optical fiber. Print both A and B rounder to 3 decimal places.
Example
Input: 2 3 1 1 1 1 0 0 0 1 1 0 6 1 3 2 3 0 0 0 2 2 0 3 2 2 3 3 3 Output: Caso #1: 2.000 0.000 Caso #2: 4.000 6.000
hide comments
jdmoyle:
2021-09-14 08:48:05
Hints:
|
|
princemishra:
2021-07-02 06:57:21
here w means that you can make w connected components in place of a single connected component =>
|
|
nyawriter:
2020-05-01 08:42:12
[solved] Last edit: 2020-05-01 08:43:42 |
|
riyadhrazzaq:
2018-10-01 09:15:48
The need for W seems unclear at first. If you get TLE for checking number of subgraph using disjoint set then just count the number of road taken in mst and subtract from total number of town. This will return the subgraphs in forrest.
|
|
sifat_15:
2018-08-21 19:52:30
Can anyone please explain 1st test case ?? |
|
jayantisswani:
2017-09-29 18:39:20
How is the cost calculated? Does the cost depend on the distance? The question is not clear and neither the testcases make it clear. |
|
nsitsk:
2016-10-15 19:25:14
Please note the "Caso" and not "Case" in output. Costed me 3 WA's. :( |
|
avisheksanvas:
2016-07-28 21:18:07
MST is getting fun! :) |
|
kejriwal:
2015-12-14 15:00:20
use scanf()/printf() in cpp...cout/cin give WA(T_T) !! |
|
Mitch Schwartz:
2014-09-16 08:55:51
For those who were confused by the problem statement (as I was at first):
|
Added by: | Eddy Cael |
Date: | 2013-10-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C CSHARP C++ 4.3.2 CPP HASK JAVA PAS-FPC PYTHON RUBY |
Resource: | Competencia CCBOL 2013 |