UVa 11138 - Nuts and Bolts Solution

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int cs=1,t,nut,bolt;
vector<vector<int> > b;
vector<int> match;
bitset<500> vis;
int aug(int u){
    if(vis[u])
        return 0;
    vis[u]=1;
    for(int i=0;i<b[u].size();i++){
        int v=b[u][i];
        if(match[v]==-1||aug(match[v])){
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    cin>>t;
    while(t--){
        cin>>bolt>>nut;
        b.assign(bolt,vector<int>());
        for(int i=0;i<bolt;i++){
            for(int j=0;j<nut;j++){
                int c;
                cin>>c;
                if(c==1)
                    b[i].push_back(j);
            }
        }
        int ans=0;
        match.assign(nut,-1);
        for(int i=0;i<bolt;i++){
            vis.reset();
            ans+=aug(i);
        }
        cout<<"Case "<<cs++<<": a maximum of "<<ans<<" nuts and bolts can be fitted together"<<endl;
    }
}