POJ 1274 The Perfect Stall

POJ_1274

    直接用匈牙利算法求二分图的最大匹配即可。

#include<stdio.h>
#include<string.h>
#define MAXD 210
int N, M, g[MAXD][MAXD], visy[MAXD], yM[MAXD];
void init()
{
    int i, j, n, x;
    memset(g, 0, sizeof(g));
    for(i = 1; i <= N; i ++)
    {
        scanf("%d", &n);
        for(j = 0; j < n; j ++)
        {
            scanf("%d", &x);
            g[i][x] = 1;
        }
    }
}
int searchpath(int cur)
{
    int i;
    for(i = 1; i <= M; i ++)
        if(g[cur][i] && !visy[i])
        {
            visy[i] = 1;
            if(yM[i] == -1 || searchpath(yM[i]))
            {
                yM[i] = cur;
                return 1;
            }
        }
    return 0;
}
void solve()
{
    int i, j, cnt = 0;
    memset(yM, -1, sizeof(yM));
    for(i = 1; i <= N; i ++)
    {
        memset(visy, 0, sizeof(visy));
        if(searchpath(i)) ++ cnt;
    }
    printf("%d\n", cnt);
}
int main()
{
    while(scanf("%d%d", &N, &M) == 2)
    {
        init();
        solve();
    }
    return 0;
}