PDA

View Full Version : [Q] Thử sức đầu xuân ! The loai LAP LICH


theanhkct
02-02-2003, 23:05
Mình có bài toán này rất hay, mong sự đóng góp của các bậc cao thủ võ lâm thử sức
Công Trường
Tại công trường xây dựng có N công việc (0<N<=100). Các công việc được đánh số thứ tự 1,2,..,N. Mỗi công việc cần một đơn vị thời gian thi công . Để thi công công việc P cần phải xây xong một số công việc P1,P2,…,Pk nào đó. Khi đó các công việc P1,P2,…,Pk gọi là công việc trước của công việc P. Những công việc không bị rằng buộc trước sau thì được thi công đồng thời.
Yêu cầu : Hãy đưa ra một lịch trình thi công để công trình hoàn thành sớm nhất. Số đơn vị thời gian để hoàn thành công trình và trong từng đơn vị thời gian thi công những công việc nào.
Dự liệu vào lấy từ file văn bản XAYDUNG.INP, gồm N dòng. Dòng thứ I trong N dòng ghi số k số nguyên dương I1,I2,..,Ik có nghĩa là các công việc I1,I2,..,Ik là các công việc trước của công việc I .(Nếu k=1 và I1=0 thì có nghĩa là công việc I không có công việc nào trước nó cả ).
Kết quả đưa ra file văn bản XAYDUNG.OUT, dòng đầu tiên ghi số S là số đơn vị thời gian cần thiết để thi công công trình. Dòng thứ M trong S dòng tiếp theo ghi t số nguyên dương R1,R2,…,Rt là các công việc được thi công đồng thời tại đơn vị thời gian thứ M.


Trả lời sớm để khai bút thử sức đầu xuân
theanhkct
03-02-2003, 13:50
Sao mà không ai giải được vậy. Bài này dễ thôi mà, admin đi đâu hết rồi
theanhkct
03-02-2003, 22:09
Zero oi! co giai duoc khong
maths_chv
04-02-2003, 21:17
Bài này không khó đâu, Bạn đưa về Đồ Thị và dùng Thuật toán " Thứ tự Tô pô" đánh số thứ tự lại các đỉnh của đồ thị sao cho các cung của Đồ thị được nối từ đỉnh có số thứ tự nhỏ đến đỉnh có số thứ tự lớn là được, kết quả sẽ cho ra thời gian tối ưu. Không tin cứ thử xem
ureka
05-02-2003, 21:56
Bài này không thể nào giải được! Tại vì file .INP của bạn bị thiếu thông số về thời gian của từng công việc. Cách tổ chức file .INP chưa hợp lý. Nếu có ai giải được bài này với dữ liệu như trên tôi xin tặng 10 cái MP3...OK