Участник:Andriygav/QUEST4

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <vector>
#include <iostream>
using namespace std;
 
bool find_match(int i, const vector<vector<int>> &w, vector<int> &mr, vector<int> &mc, vector<int> &seen){
    for(int j = 0; j < w[i].size(); j++){
        if(w[i][j] && !seen[j]){
            seen[j] = true;
            if(mc[j] < 0 || find_match(mc[j], w, mr, mc, seen)){
                mr[i] = j;
                mc[j] = i;
                return true;
            }
        }
    }
    return false;
}
 
int matching(const vector<vector<int>> &w, vector<int> &mr, vector<int> &mc){
    mr = vector<int>(w.size(), -1);
    mc = vector<int>(w[0].size(), -1);
 
    int ct = 0;
    for(int i = 0; i < w.size(); i++){
        vector<int> seen(w[0].size());
        if(find_match(i, w, mr, mc, seen)){
        	ct++;
        }
    }
    return ct;
}
 
int main(){
    int t;
    cin >> t;
    while(t--){
    	vector<vector<int>> adj(120, vector<int>(120, 0));
		vector<int> foo(120), bar(120);
		int n;
        cin >> n;
        for(int i = 0; i< n; i++){
	        while (n--) {
	            int x, y;
	            cin >> x >> y;
	            adj[x][y] = 1;
	        }
        }
        int res = matching(adj, foo, bar);
        cout << res << endl;
    }
    return 0;
}