CHROMATIC CARGO

Bài tập lớn · Minh họa thuật toán tô màu đồ thị

Khoang chứavật chất lạ

Phi hành gia mang về nhiều mẫu vật chất, chương trình tự chia chúng vào các ngăn chứa. Có những cặp mẫu để chung sẽ phản ứng. Mỗi mẫu là một đỉnh, mỗi cặp phản ứng là một cạnh, và số ngăn ít nhất chính là sắc số χ(G). Xem thuật toán tham lam theo bài giảng và thuật toán quay lui xếp mẫu từng bước, rồi so sánh kết quả.

Vào phòng thí nghiệm Đọc bài toán
Mẫu vật chất
12
Cặp phản ứng
30
Số ngăn tối thiểu
4= χ(G)
Thuật toán
2so sánh

SAMPLE_SET_01KHOANG CHỨA · 12 MẪU

T −182.96°C+01.14

χ(G) = 04 / TỰ XẾPÍT NGĂN NHẤT

Cuộn để khám phá

Mô tả bài toán

Xếp 12 mẫu vật chất vào ít ngăn nhất

Sau chuyến thu thập qua các hành tinh, phi hành gia mang về 12 mẫu vật chất. Nhưng kho chứa có hạn nên cần tiết kiệm, do đó nhiều mẫu phải để chung một ngăn. Có những cặp để chung sẽ phản ứng: chất oxy hóa gặp nhiên liệu thì cháy nổ, natri gặp nước sinh khí hydro, còn phản vật chất hủy cặp với mọi mẫu khác… (chi tiết như ma trận bên dưới)

Hãy xếp các mẫu vật chất vào ngăn chứa sao cho không ngăn nào chứa cặp phản ứng, dùng ít ngăn nhất có thể.

Cặp phản ứng—0/0

Cuộn chậm để thấy từng cặp phản ứng nối thành một cạnh của đồ thị.

Mô hình bài toán

Từ khoang chứa đến tô màu đồ thị

Input

Số mẫu vật chất n (1 ≤ n ≤ 5000) ở dòng đầu, không cần nhập số ngăn. Sau đó là ma trận kề a của đồ thị G = (V, E): n hàng, mỗi hàng n số 0/1 cách nhau dấu cách; a[u][v] = 1 nếu mẫu u phản ứng với mẫu v (cạnh (u, v) ∈ E), ngược lại 0.

Output

Số ngăn ít nhất χ(G) và phép xếp c: V → {0, …, χ − 1}, mẫu v vào ngăn c(v) + 1. Số ngăn do chương trình tự tính.

Ràng buộc

Với mọi cặp phản ứng (u, v) ∈ E thì c(u) ≠ c(v). Ma trận kề đối xứng (a[u][v] = a[v][u]), đường chéo toàn 0 (không có khuyên u–u).

Input mẫu

        
Output: χ = 4 ngăn · 

      

    

  


  
  

    

      

        

          
O(n³)

          
    
          
    Trình duyệt không hỗ trợ WebGL nên đồ thị 3D bị tắt. Các bước thuật toán vẫn chạy ở bảng bên dưới.
    
        
    
      
    

      
    
        
    
        
    
          
    Khoang hàng
    
          
    Khoang chứa vật chất
    
          
    n = 12 · m = 30
    
          
    
          
        
    
        
        
    
          
    Output C++
    
          
          
      
        
      
        
      
      

      
      
        
      
          
          
      
        
      
        
      
          
          
      
        
      
      
      

      
      
        
      Khởi tạo
      
        
      
        
      
        
      
      
      

      
      
        
      
          
          
          
          
          
        
      
        
      
          
          
      Phím cách: chạy · ← →: từng dòng
      
        
      
        
      
      
    
      
  
      

  
  
      
    
      
      
      So sánh thuật toán
      
      
      Cùng một đồ thị, hai chiến lược
      
      
      —
      
      
      
        
      
          
      Thuật toánSố ngănSố bướcThời gianĐộ phức tạp
      
          
        
      
      
      
      
      
        
      
        
      
      
    
      
    
      
  
      

  
  
      
    
      
      
      Bộ testcase
      
      
      Kiểm thử trên bộ testcase
      
      
      —
      
      
      
      
      
      
      
        
      
          
      Testn · mMong đợiTham lamQuay luiThời gian tl / qlKết quả