2015 - TỐI ƯU HÓA LỊCH THI OLYMPIC TIN HỌC 2025

Tạo bởi: GV. Bùi Phú Khuyên

Mô tả yêu cầu

Trường đại học công nghệ Tp.HCM (HUTECH) đăng cai tổ chức Olympic Tin học cấp quốc gia vào tháng 12/2025 với số lượng thí sinh dự thi đông kỷ lục.

Ban tổ chức phải sắp xếp lịch thi cho N thí sinh vào M phòng máy khác nhau sao cho không gây quá tải hệ thống, nhưng vẫn ưu tiên sử dụng các phòng có mạng ổn định.

Mỗi phòng máy i (1 \leq i \leq M) có:

  • Sức chứa tối đa: C_i (số thí sinh tối đa có thể ngồi trong phòng)
  • Độ ổn định mạng: S_i (số nguyên, càng lớn càng ổn định)

Với K đường dây mạng 2 chiều, mỗi đường sẽ nối 2 phòng máy u và v. Các phòng nối với nhau trực tiếp hoặc qua trung gian sẽ đều thuộc cùng một cụm phòng kết nối.

Nếu một phòng quá đông các phòng cùng cụm kết nối sẽ bị chậm, vì vậy tổng số thí sinh trong mỗi cụm phòng kết nối không được vượt quá một mức L đã cho.

Yêu cầu: Hãy sắp xếp N thí sinh vào M phòng, sao cho:

  • Mỗi phòng không vượt quá sức chứa.
  • Mỗi cụm phòng kết nối không vượt quá tổng L thí sinh.

  • Tổng độ ổn định mạng tổng thể phải lớn nhất có thể, tính bằng: F = \sum_{i=1}^{M} S[i] \times X[i]

    Trong đó: • X[i] = số thí sinh được phân vào phòng i. Nếu phòng không chứa ai → X[i] = 0 → phòng không đóng góp điểm.

Nếu có nhiều cách sắp xếp thỏa mãn, hãy chọn cách có tổng độ ổn định mạng F là lớn nhất. Nếu không thể sắp xếp → Output 0.

Dữ liệu vào

  • Dòng 1: 4 số nguyên dương N M K L cách nhau bằng kí tự khoảng trắng
  • Dòng 2: M số nguyên dương từ C_1C_2 … C_m cách nhau bằng kí tự khoảng trắng là sức chứa tối đa của M phòng từ phòng 1 đến M.
  • Dòng 3: M số nguyên dương từ S_1S_2 … S_m cách nhau bằng kí tự khoảng trắng là độ ổn định mạng của phòng thứ 1 đến M.
  • K dòng tiếp theo, mỗi dòng có 2 số nguyên dương u và v cách nhau bằng kí tự khoảng trắng là đường dây mạng nối phòng u với phòng v.

Dữ liệu ra

  • Một số nguyên: → độ ổn định mạng lớn nhất có thể đạt được
  • Hoặc 0 nếu không thể xếp lịch.

Giới hạn

  • 1 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 0 \leq K \leq 100000
  • 0 \leq L \leq 100000
  • 1 \leq C_i \leq 10^9
  • 0 \leq S_i \leq 10^9

Ví dụ

Dữ liệu vào Sao chép 
7 4 2 5
3 4 2 5
10 20 5 15
1 2
3 4
Dữ liệu ra Sao chép 
130
Dữ liệu vào Sao chép 
5 3 1 3
2 3 4
10 5 20
1 2
Dữ liệu ra Sao chép 
80
Dữ liệu vào Sao chép 
10 3 2 4
3 3 3
10 5 8
1 2
2 3
Dữ liệu ra Sao chép 
0

Gợi ý/Hướng dẫn

  • Input 1:Có 2 cụm phòng kết nối, mỗi cụm có thể chứa tối đa L = 5 thí sinh

    • Cụm 1 {Phòng 1, Phòng 2} (sức chứa thực 3 + 4 = 7).

    • Cụm 2 {Phòng 3} (sức chứa thực 2 + 5 = 7). Một phương án tối ưu có thể chọn là sử dụng 2 phòng (phòng 2 , phòng 4) cho N = 7 thí sinh trong đó:

    • Phòng 2 (S=20): xếp 5 thí sinh (full cụm 1) • Phòng 4 (S=15): xếp 2 thí sinh Tổng Độ ổn định mạng lớn nhất: F=20×5+15×2=100+30=130

  • Input 2: Có 2 cụm phòng kết nối, mỗi cụm có thể chứa tối đa L = 3 thí sinh

    • Cụm 1 {Phòng 1, Phòng 2} (sức chứa thực 2 + 3 =5 ).
    • Cụm 2 {Phòng 3} (sức chứa thực 4)

    Một phương án tối ưu có thể chọn là sử dụng • Phòng 3 (S=20): xếp 3 thí sinh • Phòng 1 (S=10): xếp 2 thí sinh

    Tổng Độ ổn định mạng lớn nhất: F=20×3+10×2 = 80

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 2 giây
Giới hạn bộ nhớ 256 MB

Thảo luận

Bài tập trước2014
Bài tập sau