daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest May 16th, 2018 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. #define pair dsgkfsg
  10.  
  11. int n, m;
  12. int a[200][200];
  13. vector<bool> used;
  14. vector<int> pair;
  15.  
  16. bool dfs(int x) {
  17.     if (used[x])
  18.         return false;
  19.     used[x] = true;
  20.     for (int i = 0; i < m; i++)
  21.         if (a[x][i] == 1 && (pair[i] == -1 || dfs(pair[i]))) {
  22.             pair[i] = x;
  23.             return true;
  24.         }
  25.     return false;
  26. }
  27.  
  28. int main() {
  29.     cin >> m >> n;
  30.     for (int i = 0; i < n; i++)
  31.         for (int j = 0; j < m; j++)
  32.             cin >> a[i][j];
  33.     used.resize(n);
  34.     pair.resize(m);
  35.     for (int i = 0; i < (int)pair.size(); i++)
  36.         pair[i] = -1;
  37.  
  38.     for (int i = 0; i < n; i++) {
  39.         for (int t = 0; t < (int)used.size(); t++)
  40.             used[t] = false;
  41.         dfs(i);
  42.     }
  43.     int ans = 0;
  44.     for (int i = 0; i < m; i++)
  45.         if (pair[i] != -1)
  46.             ans++;
  47.     cout << ans << endl;
  48.  
  49.     return 0;
  50. }
RAW Paste Data
Top