Skip to main content

Practice · 4 of 5

Lịch thi công — đường tới hạn

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Dự án có n công đoạn; công đoạn i mất t_i ngày; m ràng buộc "công đoạn u phải XONG trước khi v BẮT ĐẦU". Công đoạn có thể chạy song song nếu không ràng buộc cấm. In số ngày SỚM NHẤT hoàn thành toàn bộ dự án. Đồ thị đảm bảo DAG. **Ràng buộc:** 1 ≤ n ≤ 100 000; 1 ≤ m ≤ 200 000; 1 ≤ t_i ≤ 10^9; 1 ≤ u, v ≤ n. Critical path: fin[v] = max(fin[u]) + t_v theo topo order.

Back to lesson: Practice: Topo Problem Set