【题解】The Perfect Stall POJ – 1274

传送门＝￣ω￣＝

思路：二分图最大匹配模板题。二分图最大匹配详见我的 “二分图最大匹配” 博客。

代码：

#include <iostream>
#include <vector>
using namespace std;
int n,m,mn,match[405],book[405],ans;
vector<int> g[405];
bool dfs(int x)
{
    for(int i=0;i<g[x].size();i++)
        if(!book[g[x][i]])
        {
            book[g[x][i]]=1;
            if(match[g[x][i]]==0||dfs(match[g[x][i]])){match[x]=g[x][i],match[g[x][i]]=x;return 1;}
        }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    while(cin>>n>>m)
    {
        mn=m+n,ans=0;
        for(int i=1;i<=mn;i++)match[i]=0,g[i].clear();
        for(int i=1,a;i<=n;i++)
        {
            cin>>a;
            for(int j=1,b;j<=a;j++)cin>>b,g[i].push_back(b+n),g[b+n].push_back(i);
        }
        for(int i=1;i<=mn;i++)
        {
            for(int j=1;j<=mn;j++)book[j]=0;
            if(!match[i])if(dfs(i))ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}