fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 35; // n ≤ 30
  5. const int M = 15; // m ≤ 10
  6.  
  7. int n, m;
  8. vector<int> canTeach[M];     // danh sách môn mà giáo viên có thể dạy
  9. bool conflict[N][N];         // conflict[i][j] = true nếu môn i và j xung đột
  10. int x[N];                    // x[i] = giáo viên dạy môn i
  11. int loadTeacher[M];          // tải hiện tại của từng giáo viên
  12. int res = 1e9;               // kết quả tốt nhất
  13. bool teachable[M][N];        // teachable[t][c] = true nếu gv t có thể dạy môn c
  14.  
  15. // Kiểm tra xem giáo viên t có thể dạy môn c hợp lệ không
  16. bool canAssign(int c, int t) {
  17.     if (!teachable[t][c]) return false;
  18.     for (int i = 1; i < c; i++) {
  19.         if (x[i] == t && conflict[i][c]) return false; // cùng gv và xung đột
  20.     }
  21.     return true;
  22. }
  23.  
  24. void Try(int c) {
  25.     for (int t = 1; t <= m; t++) {
  26.         if (canAssign(c, t)) {
  27.             x[c] = t;
  28.             loadTeacher[t]++;
  29.  
  30.             int curMax = *max_element(loadTeacher + 1, loadTeacher + m + 1);
  31.  
  32.             // nếu tải hiện tại đã >= res thì cắt nhánh
  33.             if (curMax < res) {
  34.                 if (c == n) res = curMax; // tìm được nghiệm hợp lệ
  35.                 else Try(c + 1);
  36.             }
  37.  
  38.             loadTeacher[t]--; // backtrack
  39.         }
  40.     }
  41. }
  42.  
  43. int main() {
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.  
  47.     cin >> m >> n;
  48.     for (int t = 1; t <= m; t++) {
  49.         int k; cin >> k;
  50.         while (k--) {
  51.             int course; cin >> course;
  52.             teachable[t][course] = true;
  53.         }
  54.     }
  55.  
  56.     int k; cin >> k;
  57.     while (k--) {
  58.         int a, b; cin >> a >> b;
  59.         conflict[a][b] = conflict[b][a] = true;
  60.     }
  61.  
  62.     Try(1);
  63.  
  64.     if (res == 1e9) cout << -1;
  65.     else cout << res;
  66. }
  67.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/YTMjv1
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!