fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxN = 35, maxM = 35;
  5. int n, m, prefer[maxN][maxM], conflict[maxN][maxN];
  6. int X[maxN];       // X[i] = j nghĩa là giáo viên j được giao dạy môn i
  7. int nbTeach[maxM]; // nbTeach[i] = số lượng môn học đã giao cho giáo viên i
  8. int maxLoad = 1000000;
  9.  
  10. bool check(int v, int k) {
  11.     if (prefer[k][v] == 0) return false; // Giáo viên v không dạy được môn k
  12.     for (int i = 1; i <= k - 1; i++) {   // Kiểm tra các môn đã phân công trước đó
  13.         // Môn k và i xung đột và cùng do giáo viên v dạy
  14.         if (conflict[k][i] == 1 && X[i] == v) return false;
  15.     }
  16.     return true;
  17. }
  18.  
  19. void Try(int k) { // Thử X[k] -> tìm giáo viên dạy môn k
  20.     for (int v = 1; v <= m; v++) {
  21.         if (check(v, k)) {
  22.             X[k] = v;
  23.             nbTeach[v]++;
  24.  
  25.             if (k == n) {
  26.                 int load = 0;
  27.                 for (int i = 1; i <= m; i++) {
  28.                     load = max(load, nbTeach[i]);
  29.                 }
  30.                 maxLoad = min(maxLoad, load);
  31.             } else {
  32.                 if (nbTeach[v] < maxLoad) // Nhánh cận
  33.                     Try(k + 1);
  34.             }
  35.  
  36.             nbTeach[v]--; // Quay lui
  37.         }
  38.     }
  39. }
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(NULL);
  44.  
  45.     cin >> m >> n;
  46.     for (int j = 1; j <= m; j++) {
  47.         int numPrefer;
  48.         cin >> numPrefer;
  49.         for (int i = 1; i <= numPrefer; i++) {
  50.             int preferClass;
  51.             cin >> preferClass;
  52.             prefer[preferClass][j] = 1;
  53.         }
  54.     }
  55.  
  56.     int numConflict;
  57.     cin >> numConflict;
  58.     for (int i = 1; i <= numConflict; i++) {
  59.         int class1, class2;
  60.         cin >> class1 >> class2;
  61.         conflict[class1][class2] = 1;
  62.         conflict[class2][class1] = 1;
  63.     }
  64.  
  65.     Try(1);
  66.  
  67.     if (maxLoad == 1000000) cout << -1;
  68.     else cout << maxLoad;
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/nP5trC
language:
C++14 (gcc 8.3)
created:
2 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!