Exclamation Bài toán cây khung nhỏ nhất trên đồ thị có hướng

[haihttt]

Bài toán này về cây khung nhưng lại xét trên đồ thị có hướng nên không dùng Kruskal hoặc prim để tìm, thầy giáo bảo có thuật toán riêng cho bài toán này từ những năm 60, 70 mà em tìm không thấy. Vậy bác nào biết gì về nó thì cho em biết với

[casaupro]

hic em cũng đang phải làm một bài toán cây khung nhỏ nhất - thuật toán Kruskal dùng ngôn ngữ lập trình C or C++. em lại rất kém C. bác nào có thể giải quyết giúp em bài toán này không a. em xin trân thành cảm ơn

[bete]

cây khung nhưng lại xét trên đồ thị có hướng nên không dùng Kruskal hoặc prim để tìm, thầy giáo bảo có thuật toán riêng cho bài toán này từ những năm 60, 70
http://en.ikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
-thân

[kaishuychi]

link ko dùng dc Pro ơi
Pro nào biết làm bài toán xây dựng mạng tiết kiệm nhất không ạ?

[=========> Bổ sung bài viết <=========]

Bài Toán:
Trên một nền phẳng với hệ toạ độ Decattes vuông góc đặt n máy tính, máy tính thứ i được đặt ở toạ độ (Xi,Yi) Cho phép nối thêm các dây cáp mạng nối giữa từng cặp máy tính. Chi phí nối một dây cáp mạng là tỉ lệ thuận với khoảng cách giữa hai máy tính cần nối. Hãy tìm cách nối thêm các dây cáp mạng để cho máy tính trong toàn mạng là liên thông và chi phí nối mạng là nhỏ nhất.
Tương tự như trên nhưng ban đầu đã có sẵn một số cặp máy tính nối rồi, cần cho biết cách nối thêm ít chi phí nhất