Bellman-Ford: Truy vết Chu trình Âm
Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (trọng số có thể âm). Hãy kiểm tra xem đồ thị có chứa chu trình trọng số âm hay không. Nếu có, hãy tìm và in ra các đỉnh th…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: stl, pointers, trees and graphs.
Nội dung đề bài
Mô tả bài toán
Mô tả bài toán
Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (trọng số có thể âm). Hãy kiểm tra xem đồ thị có chứa chu trình trọng số âm hay không. Nếu có, hãy tìm và in ra các đỉnh thuộc một chu trình âm bất kỳ theo đúng thứ tự duyệt.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. 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àostdoutvà 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.
Input
- Dòng đầu tiên gồm 2 số nguyên N, M (1 ≤ N ≤ 2500, 1 ≤ M ≤ 5000).
- M dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, w biểu thị cạnh có hướng từ u đến v với trọng số w (1 ≤ u, v ≤ N, -109 ≤ w ≤ 109).
Output
- Nếu không có chu trình âm, in ra
NO. - Nếu có, dòng đầu in ra
YES, dòng thứ hai in ra dãy các đỉnh tạo thành chu trình (bắt đầu và kết thúc tại cùng một đỉnh, thể hiện chu trình khép kín).
Ràng buộc
- Thời gian: 1.0s. Bộ nhớ: 256MB.
Ví dụ 1
Input
4 5
1 2 1
2 3 2
3 1 -4
3 4 1
4 1 2Output
YES
1 2 3 1Giải thích
Dữ liệu đầu vào mẫu và kết quả tương ứng theo đúng đặc tả giải thuật.
Ví dụ 2
Input
3 3
1 2 1
2 3 2
3 1 1Output
NOGiải thích
Dữ liệu kiểm thử trường hợp biên và kết quả trả về tương ứng.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.