peltorator

!Атомный Кун

Mar 29th, 2019
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int N = 300005;
  2.  
  3. int curcol, used[N], covered[N], match[N];
  4. vector<int> g[N];
  5.  
  6. bool dfs(int v)
  7. {
  8.     used[v] = curcol;
  9.     for (int u : g[v])
  10.         if (match[u] == -1)
  11.         {
  12.             covered[v] = 1;
  13.             match[u] = v;
  14.             return 1;
  15.         }
  16.     for (int u : g[v])
  17.         if (used[match[u]] != curcol && dfs(match[u]))
  18.         {
  19.             covered[v] = 1;
  20.             match[u] = v;
  21.             return 1;
  22.         }
  23.     return 0;
  24. }
  25.  
  26. void kuhn(int n)
  27. {
  28.     curcol = 0;
  29.     for (int i = 0; i < n; i++)
  30.         used[i] = 0, match[i] = -1, covered[i] = 0;
  31.     while (true)
  32.     {
  33.         curcol++;
  34.         bool ch = 0;
  35.         for (int i = 0; i < n; i++)
  36.             if (!covered[i] && used[i] != curcol)
  37.                 ch |= dfs(i);
  38.         if (!ch)
  39.             break;
  40.     }
  41. }
RAW Paste Data