Link đề bài: http://www.vnoi.info/problems/show/RELINETS/
Đề bài:
Cho đồ thị n đỉnh m cạnh mỗi cạnh có trọng số c. Bạn phải tạo 1 đồ thị sao cho bỏ đi 1 cạnh bất kì đồ thị vẫn liên thông. trọng số của đồ thị = tổng các trọng số cạnh. Tính trọng số bé nhất của đồ thị đảm bảo yêu cầu bài toán.
Input:
Gồm nhiều test case: n, m - số đỉnh và số cạnh. m = n = 0 => kết thúc bộ test. m dòng tiếp theo, u - v - w là cạnh nối đỉnh u - v có trọng số w
Output:
Mỗi test case gồm 1 dòng : Nếu có đáp án thì xuất : “The minimal cost for test case p is c.” - p là thứ tự của test case, c là đáp án của bài toán. Ngược lại, xuất : “There is no reliable net possible for test case p.”.
Giới hạn:
n <= 15, m <= 20