Hướng dẫn giải của Atcoder Educational DP Contest G - Longest Path
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Độ phức tạp thời gian: ~O(N + M)~
Bài này đơn giản chỉ cần sử dụng thuật toán DFS trên đồ thị.
Định nghĩa ~dp[i]~ là độ dài đường đi có hướng dài nhất xuất phát từ ~i~. Chú ý cách tối ưu cấu trúc con: Độ dài đường đi có hướng dài nhất xuất phát từ ~i~ = độ dài đường đi dài nhất lớn nhất xuất phát từ một trong các con của ~i~ cộng thêm ~1~.
Hướng dẫn cài đặt:
#include <bits/stdc++.h> using namespace std; vector<int> dp(100001); vector<vector<int>> adj(100001); int dfs(int x) { if (dp[x]) return dp[x]; for (auto e : adj[x]){ dp[e] = dfs(e); dp[x] = max(dp[e] + 1, dp[x]); } return dp[x]; } int main(){ int n,m; cin >> n >> m; for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); } for (int i = 0; i < n; ++i) { dfs(i); } int ans = 0; for (int i = 0;i < n; ++i) { ans = max(dp[i], ans); } cout << ans; }
Bình luận
Mọi người cho em hỏi, giảm a và b đi để làm gì ạ?
hình như là để đỉnh bắt đầu từ 0 thay vì 1