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

Your feedback is our precious!

Or call +88 02 9853138 for support