DCP-344: Repairing Road Back to All Problems

Medium Graph Theory > Minimum Spanning Tree

In middle east there is famous country having **N** towns. Every people in every towns wants to visit other people in different towns as they want to form friendship among everyone. But due to a sudden disaster, the roads between each town got destroyed. Also there are **M** companies who have some machine to construct a road. Each company machines have a fitness value **C** and each company propose to construct a road between town **A** and town **B**. Now **Mr. Shakil** is the chief engineer of constructing some roads for the country, and he wants to select minimum company such that any town people can go any town and total fitness of the machine should be maximized. He is in a dilemma how to select such companies. So he asked for your help. Input: ------ First line of input is a number **T (1 <= T <= 10)**. Each case starts with a line containing an integer **n (2 <= n <= 100000)** denoting number of towns and **m (n <= m <= 100000)** donating the number of company. Next m line contain three integer **u (1 <= u <= n), v (1 <= u <= n, v != u)** and **f((1 <= f <= 100000000)),** that’s mean ith **(1 <= i <= m)** company wants to construct a road between town **u** and **v** and fitness value of their machine is **f**. You can assume that ans is always possible. Output: ------- For each case of input, print the case number as **"Case #: x y"**, # is replaced by the case number starting from 1 and x is replaced by the minimum number of company need and y replaced by the maximum fitness value can make by the minimum number of company. Sample Input ------------ 1 3 3 1 2 1 2 3 2 3 1 3 Sample Output ------------- Case 1: 2 5

Problem Setter:

MD Musfiqur Rahman Sanim

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 1.00
C++14 2.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 Morass Cpp14 0.04s
02 tasnidmahin Cpp 0.06s
03 tariqiitju Cpp14 0.06s
04 sazal_dev Cpp 0.06s
05 I_See_You Cpp14 0.06s
06 mno123 Cpp 0.06s
07 Zeronfinity Cpp14 0.06s
08 feodorv C 0.07s
09 ksohan Cpp 0.07s
10 nayan32biswas Cpp14 0.07s
11 Brokenlog Cpp14 0.07s
12 Aman_khan Cpp 0.07s
13 as_couple Cpp14 0.07s
14 nafiz0080 Cpp14 0.07s
15 Jisancse Cpp14 0.07s
16 pulak_ict_mbstu Cpp14 0.08s
17 SakibAlamin Cpp14 0.08s
18 shaft Cpp 0.08s
19 njrafi Cpp 0.08s
20 Double_O Cpp14 0.08s
21 Ishrak Cpp 0.08s
22 ssavi Cpp14 0.08s
23 prodipdatta7 Cpp14 0.08s
24 prateepm Cpp14 0.09s
25 Mahmudul_Tushar Cpp 0.10s
26 dmehrab06 Cpp 0.11s
27 mahbubcseju Cpp14 0.13s
28 AlaminJust Cpp14 0.13s
29 alttlprgrmmng Cpp 0.13s
30 Masum_ice Cpp14 0.13s
31 swapnil Cpp14 0.14s
32 Faizul_BU Cpp 0.16s
33 moshiur_cse15 Cpp14 0.17s
34 hrOarr Cpp14 0.18s
35 FariD Cpp14 0.18s
36 jamil993 Cpp14 0.20s
37 ittehad Cpp 0.20s
38 Mr_adnan Cpp14 0.21s
39 mesuyashky Cpp14 0.22s
40 ikaadil Cpp 0.29s
41 nasif2587 Cpp14 0.92s
42 haasib Cpp 0.96s
43 shuvo_mbstu Cpp 0.98s
44 Islam_Rafat Cpp14 1.05s
45 emrul Cpp14 1.05s

Your feedback is our precious!

Or call +88 02 9853138 for support