Đối với một đồ thị đầy đủ , nếu có và chỉ có duy nhất một cây khung nhỏ nhất (MST) là , thì ta nói đồ thị đầy đủ được mở rộng từ cây .
Cho một cây , hãy tìm đồ thị đầy đủ có tổng trọng số cạnh nhỏ nhất mà có thể được mở rộng từ .
Dữ liệu:
Dòng đầu tiên biểu thị số đỉnh của cây .
dòng tiếp theo, mỗi dòng gồm ba số nguyên , mô tả một cạnh nối có trọng số là .
Đảm bảo dữ liệu đầu vào tạo thành một cây.
Kết quả:
Xuất ra duy nhất một số, biểu thị tổng trọng số các cạnh của đồ thị đầy đủ nhỏ nhất tìm được.
