POJ 1274 The Perfect Stall

题意：有n只牛，m个牛圈（大概是），告诉你每只牛想去哪个牛圈，每个牛只能去一个牛圈，每个牛圈只能装一只牛，问最多能让几只牛有牛圈住。

解法：二分图匹配。匈牙利裸题……

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

const int maxn = 205;

int n, m;

vector <int> g[maxn];

int from[maxn], tot;

bool use[maxn];

bool match(int x)

{

    for(int i = 0; i < g[x].size(); i++)

        if(!use[g[x][i]])

        {

            use[g[x][i]] = true;

            if(from[g[x][i]] == -1 || match(from[g[x][i]]))

            {

                from[g[x][i]] = x;

                return true;

            }

        }

    return false;

}

int hungary()

{

    tot = 0;

    memset(from, 255, sizeof from);

    for(int i = 1; i <= n; i++)

    {

        memset(use, 0, sizeof use);

        if(match(i))

            tot++;

    }

    return tot;

}

int main()

{

    while(~scanf("%d%d", &n, &m))

    {

        for(int i = 1; i <= n; i++)

            g[i].clear();

        for(int i = 1; i <= n; i++)

        {

            int k;

            scanf("%d", &k);

            while(k--)

            {

                int x;

                scanf("%d", &x);

                g[i].push_back(x);

            }

        }

        printf("%d\n", hungary());

    }

    return 0;

}