1. Bài Toán Con:
Cho đồ thị có hướng không chu trình (DAG) gồm n đỉnh và m cạnh, mỗi đỉnh có A[i] đồng xu vàng. Bạn có thể bắt đầu và kết thúc hành trình ở bất kì đỉnh nào. Tính số đồng xu lớn nhất mà bạn có thể thu được.
- Ở bài toán này, đầu tiên ta sẽ sort các đỉnh theo topo để có mảng topo order của đồ thị.
- Lúc này ta chỉ cần áp dụng quy hoạch động trên mảng topo này để giải bài toán.
1. Bài Toán Chính:
- Do đồ thị đề bài cho chưa là đồ thị DAG nên trước hết ta sẽ biến bài toán này thành bài toán con trên bằng phương pháp nén đồ thị có hướng thành DAG.
- Nhận thấy khi ta đi đến 1 đỉnh bất kì trong 1 thành phần liên thông mạnh, ta có thể lấy toàn bộ số xu vàng ở cả thành phần liên thông mạnh này và tiếp tục đi tiếp ở 1 đỉnh bên trong thành phần liên thông mạnh. Từ đây ta sẽ nén 1 thành phần liên thông mạnh thành một đỉnh trong đồ thị mới.
- Sau khi nén xong ta sẽ thực hiện giống với bài toán con bên trên để giải.
- Gợi ý cách nén:
-> Gọi scc[i] là số thứ tự thành phần liên thông mạnh chứa đỉnh i, dp[i] là đáp án tới thành phần liên thông mạnh i.
-> Đầu tiên ta sẽ thực hiện DFS để tìm thành phần liên thông mạnh, lúc này mỗi khi duyệt đến đỉnh i, gán scc[i] = số thứ tự thành phần liên thông mạnh đang xét, dp[scc[i]] += A[i].
-> Lúc này với mỗi cạnh (u,v) ở đồ thị ban đầu, ta sẽ có cạnh (scc[u],scc[v]) ở đồ thị mới.
shiron104
Created at
15 likes