Cây khung nhỏ nhất có hướng (Thuật toán Chu-Liu/Edmonds)

Mô tả bài toán

Cho đồ thị có hướng gồm N đỉnh (được đánh số từ 0 đến N-1) và M cạnh có trọng số không âm. Cho một đỉnh gốc R.

Một Cây khung có hướng (Directed MST / Arborescence) có gốc tại R là một đồ thị con gồm các cạnh của đồ thị sao cho:

• R có thể đi tới mọi đỉnh khác trong đồ thị thông qua các cạnh này.
• Mọi đỉnh $v

eq Rđều có đúng một cạnh đi vào (in-degree = 1$).

• Không tồn tại chu trình có hướng.

Yêu cầu: Tính tổng trọng số nhỏ nhất của một cây khung có hướng có gốc tại R. Nếu không thể vươn tới tất cả các đỉnh từ R, in ra -1.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên N, M, R (1 ≤ N ≤ 100, 0 ≤ M ≤ 10,000, 0 ≤ R < N).
• M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w đại diện cho một cạnh có hướng từ u đến v với trọng số w (0 ≤ u, v < N, 0 ≤ w ≤ 10⁶).

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng trọng số nhỏ nhất của Arborescence gốc R, hoặc -1 nếu không tồn tại.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 2000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.