ITSA 桂冠賽 [Problem B7-中] The Maximum Bottleneck Spanning Tree

題目來源：http://140.116.249.152/e-Tutor/mod/programming/view.php?id=23652

[Problem B7-中] The Maximum Bottleneck Spanning Tree

成績: 0 / 倒扣: 0.8

Time Limit: 3 second
Problem Description

● English
Let G = (V, E) be a graph to denote a communication network, in which the nodes represent sites that want to communicate. Each edge eis a communication link with a given available bandwidth b(e). For each pair of nodes u, v, we want to select a single u-v path P on which the pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the values of b(P).
It is very complicated to keep track of a path for each pair of nodes. Thus, we want to find a spanning tree T of G such that for every pair of nodes u, v, the unique u-v path in the tree can attain the best achievable bottleneck rate for u, v in G. Please write a program to construct a spanning tree T in which, for each u, v in V, the bottleneck rate of the u-v path in T is as large as possible among all possible spanning trees.
● Chinese
令 G = (V, E) 為一個圖形代表通訊網路，其中點代表通訊站，而邊代表連結二站的通訊線，每一個邊 e 皆設有一個頻寬 b (e) 表示此通訊線的最高傳輸量。任二點 u , v, 我們可以選擇一條 u -v 路徑 P ，這條路徑的瓶頸 b (P) 定義為這條路徑所有邊中的最小頻寬， u 和 v 的最佳連結路徑為所有 u -v 路徑中具有最大瓶頸的路徑。
對任意二點都紀錄其最佳連結路徑是很複雜的工作，因此我們想要找出一個生成樹，使得 u 和 v 在此生成樹的唯一路徑具有最佳的瓶頸值。請撰寫一個程式找出一個生成樹 T ，使得 T 中的任意 u -v 路徑的瓶頸在所有生成樹中是最佳的 。

Technical Specification

● English

• All the given numbers are integers and there is no sign.

● Chinese

• 每個所給數字皆為整數且無正負符號

Input Format

● English
The first line is an integer which indicates the number of test cases. Each test case contains m+1 lines defining an n-node graph. The first line consists of two integers. The first integer is n, 1 ≤ n ≤ 1000, which is the number of nodes in the graph. The nodes are given by their unique labels which are integers from 0 to n-1. The second integer is m, n ≤ m ≤ n(n-1)/2, which is the number of edges in the graph. For the next m lines, each line consists of three numbers x, y, and b((x,y)) separated by a space indicating the edge (x, y) and the bandwidth of (x,y).
● Chinese
第一列是 一個 整數代表測試資料有幾筆。每一筆測試資料包含 m +1 列定義一個圖形，第一列是二個數字 n 和 m ，第一個數字 n 表示此圖的節點數， 1 ≤ n ≤ 1000 ，每一個節點用一個數字唯一代表， n 個點的編號由 0 到 n -1 ，第二個數字 m 表示此圖的邊數， n ≤ m ≤ n(n-1)/2 ，剩下的 m 列標示此圖的邊，每一列都含三個數字以空白隔開，分別是 x ， y 和 b ((x,y)) 代表一個邊 (x, y) 和它的頻寬 b ((x,y)) 。

Output Format

● English
For each test case, output the sum of each b(e) for e in the spanning tree T in one line.
● Chinese
針對每一筆測試資料，輸出此生成樹所有邊的頻寬和。

Example

Sample Input:	Sample Output:
2 5 7 0 1 3 1 2 1 1 3 8 2 3 10 2 4 5 3 4 9 4 0 6 8 12 0 2 9 0 4 4 1 2 3 1 5 6 2 3 5 2 4 8 3 4 3 3 5 7 5 7 4 5 6 1 6 4 3 6 7 4	33 43

這題是Maximum Spanning Tree的問題，只是他要找的是阻抗值最大的cost，可以使用Kruskal 演算法來完成，判斷cycle的方法是用Disjaint Set。