Advertisement
Vince14

/<> 11377 (maximum bipartite matching multiple possible)

Oct 28th, 2023
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<int , int>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 1005;
  23.  
  24. int n, m, k, ans = 0;
  25. vector<int> v[MAXN];
  26. vector<bool> visited;
  27. vector<int> work;
  28.  
  29.  
  30. bool dfs(int cur){
  31.     if(visited[cur]){
  32.         return false;
  33.     }
  34.     visited[cur] = true;
  35.     for(auto nxt : v[cur]){
  36.         if(work[nxt] == -1 || dfs(work[nxt])){
  37.             work[nxt] = cur;
  38.             return true;
  39.         }
  40.     }
  41.     return false;
  42. }
  43.  
  44. int main() {
  45.     FAST;
  46.     cin >> n >> m >> k;
  47.     for(int x, i = 0; i < n; i++){
  48.         cin >> x;
  49.         for(int y, j = 0; j < x; j++){
  50.             cin >> y;
  51.             y--;
  52.             v[i].push_back(y);
  53.         }
  54.     }
  55.     work.assign(m, -1);
  56.     for(int i = 0; i < n; i++){
  57.         visited.assign(n, false);
  58.         if(dfs(i)){
  59.             ans++;
  60.         }
  61.     }
  62.     for(int i = 0; i < n && k > 0; i++){
  63.         visited.assign(n, false);
  64.         if(dfs(i)){
  65.             ans++;
  66.             k--;
  67.         }
  68.     }
  69.     cout << ans << "\n";
  70. }
  71.  
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement