http://acm.hdu.edu.cn/showproblem.php?pid=1068题目没说有多少个学生，所以我设为1000，AC了。
#include <iostream>
using namespace std;
const int M=1000;
bool g[M][M];
bool visit[M];
int link[M];
int n,k;
bool find(int i)
{
int j;
for(j=0;j<n;j++)
{
if(g[i][j] && !visit[j])
{
visit[j]=true;
if(link[j]==-1 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,res,t,m;
char a,b;
while(cin>>n)
{
memset(g,0,sizeof(g));
memset(link,-1,sizeof(link));
res=0;
for(t=0;t<n;t++)
{
cin>>i>>a;
cin>>a>>m>>b;
while(m--)
{
cin>>j;
g[i][j]=true;
}
}
for(i=0;i<n;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<n-res/2<<endl;
}
return 0;
}posted on 2011-09-13 19:24
大大木马 阅读(174)
评论(0) 编辑 收藏 引用