Rất xin lỗi mọi người vì đến tận hôm nay em mới có đủ thời gian để viết post này. Cảm ơn mọi người đã cổ vũ cho đội tuyển
@pirate:
Thuật toán của em trong bài RACE là như sau.
- Đặt 0 là gốc của cây, tiến hành DFS để xác định quan hệ cha/con trên cây
- Đầu tiên, xét cách làm không tối ưu với độ phức tạp O(NK): gọi F[x][y] là số đường nhỏ nhất cần đi để có 1 đường xuất phát từ 1 con của x và kết thúc tại x, và độ dài đường đi đó đúng bằng y. Việc tính toán và cập nhật trong phần này không quá phức tạp.
- Từ cách làm trên, nhận thấy vấn đề nằm ở việc với mỗi u, cần quản lí 1 tập các đường đi từ con của u đến u (gọi là path[u], và tổng số lượng các phần tử trong các path[u_i] không vượt quá N). Cho nên, để cải tiến, cần sử dụng cấu trúc dữ liệu quản lí path[u] thực hiện được 2 thao tác:
+ Truy vấn tìm 1 đường có độ dài x km và đi qua ít con đường nhất
+ Với 2 nút u, v trong đó u là cha của v, cần "ghép" path[u] và path[v] thành 1 tập
Nếu thực hiện trực tiếp việc dồn từng phần tử của v vào u, trong tình huống xấu nhất sẽ cần dồn O(N^2) phần tử. Với việc luôn dồn từ tập nhỏ hơn sang tập lớn hơn, có thể chứng minh được số phần tử cần di chuyển trong tình huống xấu nhất vào khoảng O(N log N). Ngoài ra, trong bài em sử dụng BST (STL set trong C++) để quản lí các path[u_i], nên độ phức tạp trong thuật toán của em là O(N (log N)^2)
Anh có thể tham khảo kĩ thuật tương tự trong các bài
http://vn.spoj.pl/problems/STRAVEL/
http://main.edu.pl/en/archive/oi/18/rot
Được ưa thích: 0
