TAILIEUCHUNG - GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CÁC BÀI TẬP KHÁC

Bài 1: Một khóa học gồm N môn học, môn học i phải học trong ti ngày. Giữa các môn học có mối quan hệ trước/sau: có môn học chỉ học được sau khi đã học một số môn học khác. | CÁC BÀI TẬP KHÁC Bài 1 Một khóa học gồm N môn học môn học i phải học trong ti ngày. Giữa các môn học có mối quan hệ trước sau có môn học chỉ học được sau khi đã học một số môn học khác. Mối quan hệ đó được thể hiện bởi một mảng hai chiều A i j i j 1 . N trong đó A i j 1 0 và A i i bằng 0 với mọi i A i j 1 khi và chỉ khi môn học i phải được dạy xong trước khi học môn j ngày kết thúc môn i phải trứơc ngày bắt đầu môn j . Môn học i phải dạy trước môn học j nếu có một dãy môn học i1 i2 . ik sao cho a it it 1 1 1 t k-1 i1 i và ik j. Nếu có một nhóm các môn học từng đôi một không có quan hệ trước sau thì trong mỗi ngày về nguyên tắc ta có thể học đồng thời tất cả những môn học này nếu không vi phạm quan hệ với các môn học khác . Mảng A i j được gọi là bế tắc nếu có một dãy các môn học i1 i2 . ik k 1 mà môn i1 phải dạy trước môn i2 môn i2 phải dạy trước môn i3 . môn ik-1 phải dạy trước môn ik môn ik phải dạy trước môn i1. Hãy viết chương trình với tên làm các việc sau 1. Hãy xét xem mảng A có bế tắc hay không. 2. Nếu mảng A không bế tắc hãy tính xem khóa học có thể kết thúc trong thời gian nhanh nhất là bao nhiêu ngày. 3. Theo các học bảo đảm thời gian hoàn thành ngắn nhất ở câu 2 hãy tính xem một học sinh trong quá trình học phải học đồng thời trong một ngày nhiều nhất bao nhiêu môn. Dữ liệu vào được cho bởi file text có tên trong đó số N ghi ở dòng thứ nhất trong nhóm N dòng tiếp theo dòng thứ i ghi N số A i 1 . A i N dòng cuối cùng ghi N số nguyên dượng ti không lớn hơn 30 1 i N N 30. Kết quả ghi ra file như sau dòng thứ nhất ghi số 1 0 tùy theo mảng A bế tắc không bế tắc. Nếu dòng thứ nhất ghi số 0 ta mới ghi tiếp kết quả câu 2 và 3. Kết quả câu 2 ghi tiếp vào file N 1 dòng như sau dòng dầu ghi số T là số ngày tối thiểu có thể hoàn thành khóa học tiếp theo là N dòng trong đó dòng thứ i ghi 2 số X Y với ý nghĩa môn học thứ i học từ ngày thứ X đến ngày thứ Y chú ý rằng Y - X ti - 1 . Kết quả câu 3 ghi tiếp vào file như sau dòng thứ

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.