ddd.cpp

这个 是 关于 一个 回溯法 做 的 最 大 团问题

#include<stdio.h>   
#include<string.h>
int joint[50][50];
int Size;
int MAX;
int DP[50];
bool find;

int reachEnd(int start,int sets[])//返回－1表示邻接顶点集已经为空集，否则返回第一个公共顶点。
{	
	int lp;
	for(lp=start ; lp<Size ; lp++)
		if(sets[lp])
			return lp;
	return -1;
}
void DFS(int Visit[], int start ,int depth )
{
    int loop; 
	int first;
	int sets[50],SET[50];
	memcpy(sets,Visit,Size*4);
	memcpy(SET,Visit,Size*4);
	if((first=reachEnd(start,sets))==-1)
	 {
		 if(depth > MAX){
			 MAX=depth;
			 find=true;
			 }
		 return ;
	 }
	while( first != -1){

     if(depth+Size-start <= MAX)//不可能找到最优解
       return ;
     if(depth+DP[first] <=MAX)//不可能找到最优解
		 return;

	 sets[first]=0;
     SET[first]=0;//从邻接顶点集中清除first顶点。
	 for(loop=first+1;loop<Size;loop++)  //合并邻接顶点集
		 if(SET[loop]==1 && joint[first][loop]==1)
			 sets[loop]=1;
		 else
			sets[loop]=0;
	 DFS(sets,first,depth+1);
	 if(find)
		 return ;
	 first=reachEnd(first,SET);//更新接点
	 }	
}
int main()
{
	int loop,lp;
	int Visit[50];
	while(scanf("%d",&Size)!=EOF && Size!=0)
	{
		for(loop=0;loop<Size;loop++)
			for(lp=0;lp<Size;lp++)
				scanf("%d",joint[loop]+lp);
	    MAX=0;
		for(loop=Size-1 ; loop>=0 ; loop--){
			find=false;
		    memcpy(Visit,joint[loop],Size*4); 
			DFS(Visit,loop,1);
			DP[loop]=MAX;
		}
		printf("%d\n",DP[0]);
	}
	return 0;
}