Advertisement
Guest User

Untitled

a guest
Mar 30th, 2015
545
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <sstream>
  2. #include <cassert>
  3. #include <memory.h>
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <vector>
  7. #include <string>
  8. #include <map>
  9. #include <algorithm>
  10. #include <string>
  11. #include <set>
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16.  
  17. const int maxn = 11111;
  18.  
  19. int n, m;
  20. int k;
  21. vector<int> e[maxn];
  22. int mt[maxn], tm[maxn];
  23. int when[maxn], tmr;
  24.  
  25. bool dfs(int v) {
  26.     if (when[v] == tmr) return 0;
  27.     when[v] = tmr;
  28.     for (int i = 0; i < (int)e[v].size(); i++) {
  29.         int to = e[v][i];
  30.         if (mt[to] == -1 || dfs(mt[to])) {
  31.             tm[v] = to;
  32.             mt[to] = v;
  33.             return 1;
  34.         }
  35.     }
  36.     /*for (int i = 0; i < (int)e[v].size(); i++) {
  37.         int to = e[v][i];
  38.         if (dfs(mt[to])) {
  39.             tm[v] = to;
  40.             mt[to] = v;
  41.             return 1;
  42.         }
  43.     }*/
  44.     return 0;
  45. }
  46.  
  47. int main() {
  48.     freopen("sociology.in", "r", stdin);
  49.     freopen("sociology.out", "w", stdout);
  50.  
  51.     int test = 0;
  52.     while (scanf("%d%d", &m, &n) == 2) {
  53.         memset(mt, -1, sizeof(mt));
  54.         memset(tm, -1, sizeof(tm));
  55.         for (int i = 0; i < n; i++) {
  56.             e[i].clear();
  57.         }
  58.  
  59.         scanf("%d", &k);
  60.         for (int i = 0; i < k; i++) {
  61.             int a, b;
  62.             scanf("%d%d", &a, &b);
  63.             e[--b].push_back(--a);
  64.         }
  65.  
  66.         /*for (int i = 0; i < n; i++) {
  67.             for (int j = 0; j < (int)e[i].size(); j++) {
  68.                 if (mt[e[i][j]] == -1) {
  69.                     mt[e[i][j]] = i;
  70.                     tm[i] = e[i][j];
  71.                     break;
  72.                 }
  73.             }
  74.         }*/
  75.  
  76.         int found = -1;
  77.         for (int run = 1; run;) {
  78.             run = 0;
  79.             tmr++;
  80.             for (int i = 0; i < n; i++) if (tm[i] == -1 && dfs(i)) run = 1;
  81.         }
  82.         for (int i = 0; i < n; i++) if (tm[i] == -1) found = i;
  83.  
  84.         printf("Case #%d: ", ++test);
  85.         if (found == -1) {
  86.             printf("There is no excessive subset of managers.\n");
  87.         } else {
  88.             tmr++;
  89.             dfs(found);
  90.             vector<int> v;
  91.             for (int i = 0; i < n; i++) if (when[i] == tmr) v.push_back(i + 1);
  92.             printf("Manager");
  93.             if (v.size() != 1) printf("s");
  94.             printf(" ");
  95.             for (int i = 0; i + 2 < (int)v.size(); i++) printf("%d, ", v[i]);
  96.             for (int i = max(0, (int)v.size() - 2); i + 1 < (int)v.size(); i++) {
  97.                 printf("%d and ", v[i]);
  98.             }
  99.             printf("%d form", v[(int)v.size() - 1]);
  100.             if (v.size() == 1) printf("s");
  101.             printf(" an excessive subset.\n");
  102.         }
  103.     }
  104.  
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement