二分圖的最大匹配，加一個(gè)源點(diǎn)，這個(gè)源點(diǎn)到左邊所有頂點(diǎn)加一條邊，權(quán)值為1. 。同理，加一個(gè)終點(diǎn)，所有右邊的定點(diǎn)到這個(gè)終點(diǎn)有條邊，權(quán)值為1. 這樣二分圖的最大匹配就轉(zhuǎn)換成了最大流問題。
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX=405;
int cap[MAX][MAX]={0};
int flow[MAX][MAX]={0};
int pre[MAX],m[MAX];
int N, M,S,T;
const int INF=10000000;
int bfs(int s)
{
memset(m,0,sizeof m);
memset(pre,0,sizeof pre);
queue<int> q;
q.push(s);
m[s]=INF;
while(!q.empty())
{
int u=q.front(); q.pop();
for(int v=0; v<=N+M+1; v++)
if(!m[v]&&cap[u][v]>flow[u][v])
{
pre[v]=u;
m[v]= m[u]>cap[u][v]-flow[u][v]?cap[u][v]-flow[u][v]:m[u];
q.push(v);
}
}
if(m[T]==0)return 0;
for(int u=T; u!=S ; u=pre[u])
{
flow[pre[u]][u]+=m[T];
flow[u][pre[u]]-=m[T];
}
return m[T];
}
int main()
{
while(cin>>N>>M)
{ memset(cap,0,sizeof cap);
memset(flow,0,sizeof flow);
for(int i=1; i<=N; i++)
{
int c,e;
cin>>c;
for(int j=1; j<=c; j++)
{
cin>>e;
e=e+N;
cap[i][e]=1;
}
}
S=0;
T=N+M+1;
for(int i=1; i<=N; i++)
cap[0][i]=1;
for(int i=1; i<=M; i++)
cap[N+i][T]=1;
int ans=0;
while(1)
{
int temp=bfs(S);
if(temp==0)break;
else ans+=temp;
}
cout<<ans<<endl;
}
system("pause");
return 0;
}