ZOJ1492 题意：给一个无向图 求最大团的大小。节点数小于50
数据有限，考虑记忆化搜索，方程很好给出。
令 Si=｛vi,vi+1.....vn｝ mc[i]表示Si最大团的大小，倒着推算。
必有mc[i]=mc[i+1]或mc[i]=mc[i+1]+1 后一种情况 新的最大团必然包含vi 剪枝也是显然的。（1）current_size+remain_vertex<=ans
(2)current_size+mc[i]<=ans
代码很简单
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100;
bool g[maxn][maxn],found;
int ans,list[maxn][maxn],n,len[maxn],mc[maxn];
void dfs(int size)
{
int i,j,k;
if(len[size]==0)
{
if(size>ans)
{
ans=size;
found=true;
}
return ;
}
for( k=0;k<len[size]&&!found;++k)
{
if(size+len[size]-k<=ans)break;
int i=list[size][k];
if(size+mc[i]<=ans)break;
for(j=k+1,len[size+1]=0;j<len[size];++j)
{
if(g[i][list[size][j]])
list[size+1][len[size+1]++]=list[size][j];
}
dfs(size+1);
} } void max_cluster()
{
int i,j;
mc[n]=ans=1;
for(int i=n-1;i>0;--i)
{
found=false;len[1]=0;
for(int j=i+1;j<=n;++j)
if(g[i][j])list[1][len[1]++]=j;
dfs(1);
mc[i]=ans;
}
}
int main()
{
freopen("t.txt","r",stdin);
while(scanf("%d",&n))
{
if(!n)return 0;
memset(g,0,sizeof(g));
memset(mc,0,sizeof(mc));
memset(list,0,sizeof(list));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int t;scanf("%d",&t);
if(t==1)g[i][j]=1;
}
max_cluster();
printf("%d\n",ans);
}
return 0;
}