hdu 1179

二分图最大匹配

AC 代码

#include <iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;


const int maxn=105;

bool visited[maxn];

int matched[maxn];

vector<int> wizard[maxn];

 int n,m;

bool dfs(int v){

    int len=wizard[v].size();
    int w;
    for(int i=0;i<len;i++){
        w=wizard[v][i];
        if(!visited[w]){

            visited[w]=true;

            if(matched[w]==-1||dfs(matched[w])){

                matched[w]=v;
                return true;
            }
        }
    }
    return false;
}

int hungary(){

    int ans=0;
    memset(matched,-1,sizeof(matched));
    for(int i=1;i<=n;i++){
        memset(visited,false,sizeof(visited));

        if(dfs(i)){
            ans++;
        }

    }
    return ans;
}

int main()
{

    int k;

    int p;
    while(scanf("%d%d",&n,&m)!=EOF){


//  this  step is very very import, if not will get WA
        for(int i=1;i<=n;i++) wizard[i].clear();
        for(int i=1;i<=m;i++){

            scanf("%d",&k);

            for(int j=0;j<k;j++){

                scanf("%d",&p);
                wizard[p].push_back(i);
            }

        }

        int ans=hungary();
        printf("%d\n",ans);
    }
    return 0;
}