POJ 1274 The Perfect Stall(二分图最大匹配)

POJ 1274 The Perfect Stall(二分图最大匹配)

http://poj.org/problem?id=1274

题意:

农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。

输入：第一行 两个整数，N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量，M 是新牛棚的牛栏数量。

第二行到第N+1行一共 N 行，每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M) 。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中，在同一行，一个牛栏不会被列出两次。

分析:

直接把奶牛看出二分图左边的点集,牛栏看成二分图右边的点集.那么本题就是求该图的最大匹配边数了.

AC代码:

#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200+10;

struct Max_Match
{
    int n,m;
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n,int m)
    {
        this->n=n;
        this->m=m;
        for(int i=1;i<=n;i++) g[i].clear();
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }

}MM;

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        MM.init(n,m);
        for(int i=1;i<=n;i++)
        {
            int num;
            scanf("%d",&num);
            while(num--)
            {
                int j;
                scanf("%d",&j);
                (MM.g[i]).push_back(j);
            }
        }
        printf("%d\n",MM.solve());
    }
    return 0;
}