Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Duy trì đường mòn (Trail Maintenance)
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526
Bài toán: Duy trì đường mòn (Trail Maintenance)
Những con bò của bác nông dân Jonh muốn được tự do đi lại giữa N (1≤N≤200) cánh đồng (đánh số 1..N) của trang trại, mặc dù giữa các cánh đồng bị ngăn cách bởi những rừng cây. Các con bò muốn sử dụng những tuyến đường mòn nối liền các cặp cánh đồng để đi. Bò có thể di chuyển trên các con đường theo cả hai chiều.
Các con bò không tự làm được đường, thay vào đó, chúng sử dụng đường đi của động vật hoang dã mà chúng phát hiện ra. Hàng tuần, các con bò cần lựa chọn một số hay tất cả các tuyến đường chúng biết để duy trì.
Đầu mỗi tuần, các con bò lại phát hiện thêm một đường đi mới của động vật hoang dã. Chúng phải quyết định tập hợp các con đường mà chúng phải duy trì sao cho trong tuần đó chúng có thể đi lại từ cánh đồng này tới cánh đồng khác một cách bất kỳ. Bò chỉ có thể sử dụng các con đường mà hiện chúng đang duy trì khi di chuyển.
Các con bò luôn mong muốn tổng chiều dài các đường mòn phải duy trì là nhỏ nhất. Bò có thể chọn duy trì bất kỳ con đường nào trong số chúng biết, dù cho đường đi đó có được duy trì ở tuần trước hay không.
Đường đi của động vật hoang dã (kể cả khi được duy trì) không bao giờ thẳng. Hai tuyến đường nối cùng một cặp cánh đồng có thể có chiều dài khác nhau. Các tuyến đường cũng có thể cắt nhau, tuy nhiên, bò không thay đổi đường đi trừ khi chúng ở trên cánh đồng.
Cứ vào đầu tuần, các con bò sẽ cho bạn biết đường đi mới của động vật hoang dã mà chúng vừa phát hiện được. Chương trình của bạn phải chỉ ra tổng ngắn nhất chiều dài các con đường mà bò cần duy trì để trong tuần đó, chúng có thể đi đến mọi cánh đồng, tất nhiên, nếu tồn tại các tuyến đường như vậy.
Input: Standard input
Dòng đầu tiên của tệp input bao gồm hai số nguyên, cách nhau bởi dấu trắng, N và W, trong đó W là số tuần mà chương trình cần tính toán. (1≤W≤6000)
Với mỗi tuần, đọc một dòng chứa thông tin về đường đi của động vật hoang dã được phát hiện. Dòng này chứa 3 số nguyên, cách nhau bởi dấu trắng, bao gồm: số hiệu các cánh đồng hai đầu đường đi và chiều dài con đường (1..10000). Số hiệu cánh đồng hai đầu tuyến đường luôn khác nhau.
Output: Standard output
Ngay sau khi biết thông tin về đường đi của động vật hoang dã mới được phát hiện, chương trình của bạn cần đưa ra một dòng trên đó bao gồm tổng chiều dài ngắn nhất của các con đường mà bò phải duy trì. Nếu không tồn tại các đường đi cho phép bò di chuyển đến mọi cánh đồng, đưa ra số -1.
Chương trình của bạn phải kết thúc ngay sau khi xử lý tuần cuối cùng.
Ví dụ:

Hạn chế:
Thời gian chạy chương trình là 1 giây
Bộ nhớ 64MB
Cho điểm:
Bạn sẽ nhận được điểm tối đa cho mỗi bộ test nếu chương trình của bạn đưa ra kết quả đúng.
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556