Co đồ thị SCC và Đường đi dài nhất trên đồ thị rút gọn DAG

Mục tiêu kiến thức

• Nắm vững kỹ thuật Co đồ thị (Graph Condensation): Biến đổi đồ thị có hướng có chu trình thành một đồ thị có hướng không chu trình (DAG) bằng cách co mỗi thành phần liên thông mạnh (SCC) thành một siêu đỉnh.
• Trọng số của mỗi siêu đỉnh bằng tổng giá trị của các đỉnh con bên trong nó.
• Áp dụng quy hoạch động trên DAG (sắp xếp Tô-pô) để tìm đường đi có tổng trọng số lớn nhất xuất phát từ bất kỳ siêu đỉnh nào.

Mô tả bài toán

Cho một đồ thị có hướng gồm N đỉnh và M cạnh. Mỗi đỉnh u có chứa một lượng tài nguyên là số nguyên V_u. Khi bạn đi qua một đỉnh, bạn có thể thu thập toàn bộ tài nguyên tại đỉnh đó (mỗi đỉnh chỉ được thu thập tối đa một lần dù đi qua nhiều lần). Bạn có thể xuất phát tại bất kỳ đỉnh nào và kết thúc tại bất kỳ đỉnh nào. Hãy tìm lượng tài nguyên lớn nhất có thể thu thập được.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N ≤ 10⁵, 0 ≤ M ≤ 2 · 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.