Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

就是最大独立!好搞!

Posted by chenxuan123456789 at 2012-08-11 17:45:41 on Problem 1466
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator