SHARE
TWEET

fast kuhn

a guest Nov 14th, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define db(x) cerr<<#x<<" == "<<x<<endl
  5. #define _ <<", "<<
  6.  
  7. mt19937_64 llrand(random_device{}());
  8.  
  9. const int INF = 0x3f3f3f3f;
  10. const int N = 105, A = 11, M = 3 * N * (1<<A);
  11.  
  12. int n, cnt, mcnt, r[M];
  13. map<string, int> m;
  14. vector<int> a[N];
  15.  
  16. bitset<1005> val[M];
  17. unordered_map<bitset<1005>, int> ms;
  18.  
  19. int b[M], x, vis[M], mat[M];
  20. vector<int> g[M];
  21.  
  22. bool match(int u) {
  23.   if (vis[u] == x) return 0;
  24.   vis[u] = x;
  25.   for (int v : g[u])
  26.     if (!b[v] or match(b[v])) {
  27.       b[v] = u;
  28.       mat[u] = 1;
  29.       return 1;
  30.     }
  31.   return 0;
  32. }
  33.  
  34. int main() {
  35.   scanf("%d", &n);
  36.   for (int i = 0; i < n; i++) {
  37.     int x;
  38.     char s[15];
  39.     scanf("%d", &x);
  40.     while (x--) {
  41.       scanf("%s", s);
  42.       if (!m.count(s)) m[s] = mcnt++;
  43.       a[i].push_back(m[s]);
  44.     }
  45.  
  46.     for (int j = 1; j < (1<<a[i].size()); j++) {
  47.       bitset<1005> xx = 0;
  48.       for (int k = 0; k < a[i].size(); k++) if ((1<<k)&j)
  49.         xx.set(a[i][k]);
  50.  
  51.       if (!ms.count(xx)) {
  52.         cnt++;
  53.         val[cnt] = xx;
  54.         ms[xx] = cnt;
  55.         r[cnt] = i;
  56.       }
  57.     }
  58.   }
  59.  
  60.   for (int i = 1; i <= cnt; i++) if (val[i].count() > 1) {
  61.     for (int j = 0; j < a[r[i]].size(); j++) {
  62.       auto xx = val[i];
  63.       int bit = a[r[i]][j];
  64.       if (!xx[bit]) continue;
  65.  
  66.       xx.reset(bit);
  67.  
  68.       g[ms[xx]].push_back(i + cnt);
  69.     }
  70.   }
  71.  
  72.   for (int i = 1; i <= cnt; i++) {
  73.     //shuffle(g[i].begin(), g[i].end(), llrand); // Pior???
  74.     random_shuffle(g[i].begin(), g[i].end());
  75.   }
  76.  
  77.   int ans = cnt;
  78.  
  79.   // fast kuhn
  80.   while (1) {
  81.     int xx = 0;
  82.  
  83.     x++;
  84.     for (int i = 1; i <= cnt; i++) if (!mat[i])
  85.       xx += match(i);
  86.  
  87.     if (xx == 0) break;
  88.     ans -= xx;
  89.   }
  90.  
  91.   /*
  92.   // kuhn normal
  93.   for (int i = 1; i <= cnt; i++) {
  94.     x++;
  95.     ans -= match(i);
  96.   }
  97.   */
  98.  
  99.   printf("%d\n", ans);
  100.   return 0;
  101. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top