SHARE
TWEET

Untitled

a guest Apr 21st, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <fstream>
  5. using namespace std;
  6.  
  7. vector < vector <int> > g(402);
  8. vector<int> mt;
  9. vector<char> used;
  10.  
  11. bool kuhn (int v) {
  12.     if (used[v])
  13.         return false;
  14.     used[v] = true;
  15.     for (int i = 0; i < g[v].size(); i++) {
  16.         int to = g[v][i];
  17.         if (mt[to] == -1 || kuhn (mt[to])) {
  18.             mt[to] = v;
  19.             return true;
  20.         }
  21.     }
  22.     return false;
  23. }
  24.  
  25. int main() {
  26.     //freopen ("matching.in", "r", stdin);
  27.     //freopen ("matching.out", "w", stdout);
  28.     int n, m, k;
  29.     cin >> n >> m >> k;
  30.  
  31.     for (int i = 0; i < k; i++) {
  32.         int x, y;
  33.         cin >> x >> y;
  34.         g[x - 1].push_back(n + y - 1);
  35.         g[n + y - 1].push_back(x - 1);
  36.     }
  37.     mt.assign(m, -1);
  38.     for (int v = 0; v < n; v++) {
  39.         used.assign(n, false);
  40.         kuhn(v);
  41.     }
  42.     int z = 0;
  43.     for (int i = 0; i < m; i++) {
  44.         if (mt[i] != -1)
  45.             z++;
  46.     }
  47.         cout << z << endl;
  48. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top