The Perfect Stall

题意：求二分图的最大匹配

解题思路：

1. 匈牙利算法（参考算法http://www.cnblogs.com/bofengqiye/archive/2012/05/02/2479809.html）

代码：

/*
ID: zc.rene1
LANG: C
PROG: stall4
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_N 200
#define MAX_M 200

int N, M;
int table[MAX_N + 1][MAX_M + 1];
int Uindex[MAX_N + 1];
int Vindex[MAX_M + 1];
int visited[MAX_M + 1];

int GetPath(int u)
{
    int v;

    for (v=1; v<=M; v++)
    {
	if (table[u][v] && visited[v] == 0)
	{
	    visited[v] = 1;
	    if (Vindex[v] == 0 || GetPath(Vindex[v]))
	    {
		Uindex[u] = v;
		Vindex[v] = u;
		return 1;
	    }
	}
    }
    return 0;
}

int DoWork(void)
{
    int ret = 0;
    int i;

    memset(Uindex, 0, (MAX_N + 1) * sizeof(int));
    memset(Vindex, 0, (MAX_M + 1) * sizeof(int));

    for (i=1; i<=N; i++)
    {
	if (Uindex[i] == 0)
	{
	    memset(visited, 0, (MAX_M + 1) * sizeof(int));
	    ret += GetPath(i);
	}
    }

    return ret;
}

int main(void)
{
    FILE *fin, *fout;
    int i, j, k, len;

    fin = fopen("stall4.in", "r");
    fout = fopen("stall4.out", "w");

    memset(table, 0, (MAX_N + 1) * (MAX_M + 1) * sizeof(int));

    fscanf(fin, "%d %d", &N, &M);
    for (i=1; i<=N; i++)
    {
	fscanf(fin, "%d", &len);
	for (j=1; j<=len; j++)
	{
	    fscanf(fin, "%d", &k);
	    table[i][k] = 1;
	}
    }

    fprintf(fout, "%d\n", DoWork());
    return 0;
}