# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int data[31][31];
int match[31];
int isin(int target,int pos[])
{
	int i;
	for(i=1;i<=pos[0];i++)
		if(pos[i]==target) return 1;
	return 0;
}
int min(int a,int b)
{
	if(a<b) return a;
	else return b;
}
int cul(int total)
{
	int c1[31],c2[31];
	int i,lone=0;
	c1[0]=c2[0]=0;
	for(i=1;i<=total;i++)
	  if(match[i]==1) c1[++c1[0]]=i;
	  else c2[++c2[0]]=i;
	for(i=1;i<=c1[0];i++)
	{
		int j,templone=0;
		for(j=1;j<=data[c1[i]][0];j++)
		{
			if(isin(data[c1[i]][j],c1)) templone++;
		}
		templone=c1[0]-templone-1;
		if(templone>lone) lone=templone;
	}
	for(i=1;i<=c2[0];i++)
	{
		int j,templone=0;
		for(j=1;j<=data[c2[i]][0];j++)
		{
			if(isin(data[c2[i]][j],c2)) templone++;
		}
		templone=c2[0]-templone-1;
		if(templone>lone) lone=templone;
	}
	return lone;
}

int deal(int now,int total)
{
	if(now==total)
	{
		return cul(total);
	}
	else
	{
		int result=deal(now+1,total);
		int i;
		for(i=now+1;i<=total;i++)
		{
		   if(match[i]!=match[now])
		   {
			   int temp=match[now];
			   match[now]=match[i];
			   match[i]=temp;
			   result=min(result,deal(now+1,total));
			   temp=match[now];
			   match[now]=match[i];
			   match[i]=temp;
		   }
		}
		return result;
	}
}
int main()
{
	char line[1024];
	int total=0,j;
	while(gets(line))
	{
		int temp[60];
		int count=0;
		int pos,i;
		char* token;
		pos=atoi(strtok(line," "));
		while((token=strtok(NULL," "))!=NULL)
		{
			temp[++count]=atoi(token);
		}
		data[pos][0]=count;
		for(i=1;i<=count;i++) data[pos][i]=temp[i];
		total++;
	}
	for(j=1;j<=total/2;j++) match[j]=1;
	for(j=total/2+1;j<=total;j++) match[j]=0;
	printf("%d\n",deal(1,total));
	return 0;
}
	

		

• Re:数据很弱，没有记录状态纯回溯就0MS AC了，不过最后loneless的那个人用的时间就是最长时间，这个可以用贪心证明的，贴代码 (63) bixiongquan 2016-06-12 10:50:30