VNEMPIRE trên VOJ

[Tran Hai Dang]

Bài này có link như sau: http://vn.spoj.pl/problems/VNEMPIRE/, bài này
anh dịch trên COCI 2007 contest 7, hồi anh pos lên VOJ thì trên đó chỉ
có test và kết quả, không có solution, thực chất bài này solution là
prim thôi, điều mấu chốt ở đây không phải là mỗi lần ta cố định được
một đỉnh mà cập nhật các đỉnh còn lại mà chỉ cập nhật đỉnh nào gần nó
nhất thôi. Giải thuật N log N, nếu chưa rõ anh sẽ nói thêm sau
Test ở đây: http://hsin.hr/coci/contest7_testdata.zip
Solution ở đây: http://hsin.hr/coci/contest7_solutions.zip

[le tue]

Anh có nhầm ko? Prim là N^2, Kruskal mới là NlogN, nhưng em thấy đồ
thì rất dày (N^2 cạnh). Chắc là phải tìm cách chỉ nối các cạnh cần
thiết.

[Tran Hai Dang]

Anh không hề nhầm, em nhìn xem, Prim này anh đã nhấn mạnh ở phần cập
nhật đỉnh đó, chỉ tìm đỉnh gần nhất đề cập nhật thôi, không cần cập
nhật tất cả, cho nên mới là N log N

[Trung Thanh]

Theo mình hiểu thì Prim với Kruskal có độ phức tạp xấp xỉ bằng nhau, là O(MlogN) hay O(MlogM). Nếu áp dụng thô thiển cho bài này, thì đều không được (vì số cạnh hiểu theo đề bài là N^2?). Mấu chốt là loại bỏ những cạnh thừa, bằng cách xử lý dấu | | --- On Sun, 6/27/10, Tran Hai Dang <tranhai...@gmail.com> wrote: