没什么好说的，直接匈牙利算法
#include<iostream>
using namespace std;
int n,m;//n为x集合，m为y集合
int map[305][305];//map[x][y]表示x,y两点之间有边相连
bool visit[305];//记录m中的i节点是否被访问过
int link[305];//记录当前n中的i节点是否与 j节点相连
bool dfs(int a)
{
int i;
for (i=1;i<=n;i++)
{
if (map[a][i]&&!visit[i])
{
visit[i]=true;
if (link[i]==0||dfs(link[i]))
{
link[i]=a;
return true;
}
}
}
return false;
}
int find()
{
int sum=0;
for (int i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if (dfs(i))sum++;
}
return sum;//最大匹配数
}
int main()
{
int t,i,j,k,x;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(map,0,sizeof(map));
memset(link,0,sizeof(link));
for (i=1;i<=n;i++)
{
scanf("%d",&j);
for (k=1;k<=j;k++)
{
scanf("%d",&x);
map[i][x]=1;
}
}
cout<<find()<<endl;
}
return 0;
}
posted on 2011-04-04 09:50
路修远 阅读(1235)
评论(0) 编辑 收藏 引用 所属分类:
路修远