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 x_{i}, y_{i} (10000 <= x_{i}, y_{i} <= 10000), the coordinates of ith 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:
20210914 08:48:05
Hints:


princemishra:
20210702 06:57:21
here w means that you can make w connected components in place of a single connected component =>


nyawriter:
20200501 08:42:12
[solved] Last edit: 20200501 08:43:42 

riyadhrazzaq:
20181001 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:
20180821 19:52:30
Can anyone please explain 1st test case ?? 

jayantisswani:
20170929 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:
20161015 19:25:14
Please note the "Caso" and not "Case" in output. Costed me 3 WA's. :( 

avisheksanvas:
20160728 21:18:07
MST is getting fun! :) 

kejriwal:
20151214 15:00:20
use scanf()/printf() in cpp...cout/cin give WA(T_T) !! 

Mitch Schwartz:
20140916 08:55:51
For those who were confused by the problem statement (as I was at first):

Added by:  Eddy Cael 
Date:  20131025 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP HASK JAVA PASFPC PYTHON RUBY 
Resource:  Competencia CCBOL 2013 