Đường Đi Dài Nhất Trên DAG Rút Gọn
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho đồ thị có hướng gồm N đỉnh và M cạnh. Xây dựng đồ thị rút gọn (condensation DAG). Trọng số mỗi đỉnh trong DAG rút gọn bằng số đỉnh trong SCC tương ứng. Tìm đường đi dài nhất trên DAG rút gọn (tổng trọng số đỉnh lớn nhất).
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
- M dòng tiếp theo: u v
Dữ liệu ra
- Một số nguyên: tổng trọng số lớn nhất trên đường đi trong DAG rút gọn.
Ví dụ
| Input | Output |
|---|---|
| 7 8\n1 2\n2 3\n3 1\n4 5\n5 4\n6 7\n7 6\n3 4 | 7 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
Community Discussion