| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
就是最大独立!好搞!#include "stdio.h"
#include "string.h"
#define M 520
int g[M][M];
int link[M];
int used[M];
int n;
int dfs(int stu)
{
int i;
for( i=0;i<n;i++)
if(!used[i]&&g[stu][i])
{
used[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=stu;
return 1;
}
}
return 0;
}
int main()
{
int m;
int a,b,i,j,l,ans;
while(scanf("%d",&n)!=EOF)
{
memset(g,0,sizeof(g));
memset(link,-1,sizeof(link));
for(i=0;i<n;i++)
{
scanf("%d: (%d)",&a,&m);
for(j=0;j<m;j++)
{
scanf("%d",&b);
g[a][b]=1;
}
}
ans=0;
for(l=0;l<n;l++)
{
memset(used,0,sizeof(used));
if(dfs(l))ans++;
}
if(ans%2)
ans+=1;
printf("%d\n",n-ans/2);
}
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator