Advertisement
Guest User

Untitled

a guest
Oct 19th, 2013
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <deque>
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>
  8.  
  9. using namespace std;
  10. typedef long long i64;
  11.  
  12. const int MAX_N = 1005;
  13. vector<int> tasks[MAX_N];
  14. bool done[MAX_N];
  15. int n;
  16. int m;
  17.  
  18. bool IsAllDone() {
  19.     for (int i = 1; i <= m; i++) {
  20.         if (!done[i]) {
  21.             return false;
  22.         }
  23.     }
  24.     return true;
  25. }
  26.  
  27. vector<int> gr[MAX_N];
  28. int mt[MAX_N];
  29. bool us[MAX_N];
  30.  
  31. bool Kuhn(int u) {
  32.     if (us[u]) {
  33.         return false;
  34.     }
  35.     us[u] = true;
  36.     for (int i = 0; i < gr[u].size(); i++) {
  37.         int v = gr[u][i];
  38.         if (mt[v] == -1 || Kuhn(mt[v])) {
  39.             mt[v] = u;
  40.             return true;
  41.         }
  42.     }
  43.     return false;
  44. }
  45.  
  46. int Solve() {
  47.     for (int i = 1; i <= n; i++) {
  48.         gr[i].clear();
  49.         for (int j = 0; j < tasks[i].size(); j++) {
  50.             int task = tasks[i][j];
  51.             if (done[task]) {
  52.                 continue;
  53.             }
  54.             gr[i].push_back(task);
  55.         }
  56.     }
  57.     memset(mt, -1, sizeof(mt));
  58.     for (int i = 1; i <= n; i++) {
  59.         memset(us, 0, sizeof(us));
  60.         Kuhn(i);
  61.     }
  62.     int res = 0;
  63.     for (int i = 1; i <= m; i++) {
  64.         if (mt[i] != -1) {
  65.             res++;
  66.             done[i] = true;
  67.         }
  68.     }
  69.     return res;
  70. }
  71.  
  72. int main() {
  73. #ifdef NOVACO
  74.     freopen("input.txt", "r", stdin);
  75.     freopen("output.txt", "w", stdout);
  76. #else
  77.     freopen("contest.in", "r", stdin);
  78.     freopen("contest.out", "w", stdout);
  79. #endif
  80.     int t;
  81.     int l;
  82.     cin >> n >> m >> t >> l;
  83.     for (int i = 1; i <= n; i++) {
  84.         int k;
  85.         cin >> k;
  86.         for (int j = 0; j < k; j++) {
  87.             int a;
  88.             cin >> a;
  89.             tasks[i].push_back(a);
  90.         }
  91.     }
  92.     int dirt = 0;
  93.     int res = 0;
  94.     for (int i = 0; i < t / l; i++) {
  95.         if (IsAllDone()) {
  96.             break;
  97.         }
  98.         int solved = Solve();
  99.         res += solved;
  100.         dirt += solved * l * (i + 1);
  101.     }
  102.     cout << res << " " << dirt << "\n";
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement