编写程序实现最大团问题

#include

#include

int a[100][100];

int n,x[100],

bestx[100],

cn=0,

bestn=0;

void Backtrack(int i)

{

if(i>n){

cout<<”\n”;

for(int j=1;j<=n;j++)

{

bestx[j]=x[j];

if(bestx[j]==1)；

cout<

}

bestn=cn;

cout<<”\n”<

return;}

int OK=1;

for(int j=1;j

if(x[j]&&a[i][j]==0){

OK=0;

break;}

if(OK){

x[i]=1;

cn++;

Backtrack(i+1);

x[i]=0;

cn–;}

if(cn+n-i>bestn){

x[i]=0;

Backtrack(i+1);}

}

int main()

{

printf(“请输入图点的个数:”);

int i;

cin>>n;

for(i=0;i<=n;i++)

{

for(int j=0;j<=n;j++)

{

a[i][j]=-1;

}

}

printf(“请输入中的各点之间相连的情况:（不相连用1表示，相连用0表示）\n”);

for(i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

if(i==j)

{

a[i][j]=1;

}

if((i!=j)&&(a[j][i]<0))

{

printf(“a(%d,%d)”,i,j);

cin>>a[i][j];

a[j][i]=a[i][j];

}

}

}

printf(“该图的点的个数为:%d\n”,n);

printf(“相连的边为:\n”);

for(i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

if((a[i][j]==1))

{

printf(“a(%d,%d) “,i,j);

}

}

printf(“\n”);

}

printf(“最大团的最优解为:\n”);

Backtrack(1);

return 0;

}