T
tmb12
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Hệ thống giao thông trong một thành phố bao gồm N nứt giao thông và M đoạn đường phố hai chiều, mỗi đoạn nối 2 nút giao thông. Các nút giao thông được đánh số từ 1 đến N và các đoạn đường phố được đánh số từ 1 đến M. Giữa 2 nút giao thông có không quá một đoạn đường phố nối chúng. Hệ thống giao thông đảm bảo sự đi lại giữa hai nút giao thông bất kỳ. Ban quản lý hệ thống giao thông giao nhiệm vụ thực hiện dự án nâng cấp tất cả các đoạn đường phố. Mọi sự đi lại theo đoạn đường phố sẽ bị cấm trong suốt thời gian thực hiện thi công nâng cấp bất cứ đoạn đường phố nào cũng là 1 ngày và trong một ngày Ban quản lý có thể tổ chức thực hiện việc thi công nâng cấp đồng thời không quá K đoạn đường phố. Để đảm bảo sự đi lại giữa 2 nút giao thông bất kỳ trong suốt thời gian thực hiện dự án, Ban quản lý cần tìm lịch thi công các đoạn đường một cách hợp lý.
Yêu cầu: Tìm lịch thi công nâng cấp tất cả các đoạn đường phố đảm bảo sự đi lại giữa hai nút giao thông bất kỳ trong suốt quá trình thực hiện dự án, đồng thời sao cho dự án được hoàn thành sau ít ngày nhất.
Dữ liệu: vào
+ Dòng đầu tiên chứa 3 số nguyên dương N, M, K (2<=N<=500; 1<=M<=20000; 1<=K<=N).
+ Dòng thứ i trong số M dòng tiếp theo chứa cặp hai số liệu của hai nút giao thông tương ứng là hai đầu mút của đoạn đường phố thứ i.
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra
+ Dòng đầu tiên ghi P là số ngày cần thực hiện theo lịch thi công tìm được (Quy ước ghi P = -1, nếu không tìm được lịch thỏa mãn yêu cầu đặt ra).
+ nếu tìm được lịch thì dòng thức i trong số M dòng tiếp theo ghi chỉ số của ngày thực hiện thi công nâng cấp đoạn đường thứ i. Các ngày trong lịch thực hiện dự án được đánh số từ 1 đến P theo đúng trình tự thời gian.
Bài này mình copy bên diendantinhoc.vn bên đó chưa ai giải được hết!
Yêu cầu: Tìm lịch thi công nâng cấp tất cả các đoạn đường phố đảm bảo sự đi lại giữa hai nút giao thông bất kỳ trong suốt quá trình thực hiện dự án, đồng thời sao cho dự án được hoàn thành sau ít ngày nhất.
Dữ liệu: vào
+ Dòng đầu tiên chứa 3 số nguyên dương N, M, K (2<=N<=500; 1<=M<=20000; 1<=K<=N).
+ Dòng thứ i trong số M dòng tiếp theo chứa cặp hai số liệu của hai nút giao thông tương ứng là hai đầu mút của đoạn đường phố thứ i.
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra
+ Dòng đầu tiên ghi P là số ngày cần thực hiện theo lịch thi công tìm được (Quy ước ghi P = -1, nếu không tìm được lịch thỏa mãn yêu cầu đặt ra).
+ nếu tìm được lịch thì dòng thức i trong số M dòng tiếp theo ghi chỉ số của ngày thực hiện thi công nâng cấp đoạn đường thứ i. Các ngày trong lịch thực hiện dự án được đánh số từ 1 đến P theo đúng trình tự thời gian.
Bài này mình copy bên diendantinhoc.vn bên đó chưa ai giải được hết!