题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1530
参考博客：http://blog.csdn.net/yjpYJP2014/article/details/52590161?locationNum=13&fps=1
http://www.cnblogs.com/zhj5chengfeng/archive/2013/07/29/3224092.html
因为自己对这方面也是刚入门，只学了最简单最暴力的DFS法，n超过100时可能gg。
这是一道裸的最大团，思路：
将n个点加入一个集合U1，遍历U1中的点，每次选择1个点P1作为最大团的第一个点，即DFS的第一层。
遍历U1中剩下的点，选出与P1相连的点，加入集合U2，每次选择U2中的一个点P2作为最大团的第二个点，即DFS的第二层。
遍历U2中剩下的点，选出与P2相连的点，加入集合U3，每次选择U3中的一个点P3作为最大团的第三个点，即DFS的第三层（因为团即最大完全子图，要求各个点两两相连，因此只要从之前的集合中选择点即可，只有这些点是与之前的点相连的）。
……
以此类推，到DFS的最后一层m，即此时的Um为空集时，递归结束，求出了一个团。返回上一层继续递归其他情况……选出其中的最大团输出。
以上是最朴素的思路，但是这样的时间复杂度太高了，所以我们考虑剪枝：
1.显然，当DFS进行到某一层x时，如果当前层数（即团内点的数量）加上集合Ux中剩下点的数量小于等于已得出的答案（即使把剩下的点全部加入团中也无法更新答案），那我们可以直接返回上一层。
2.倒序遍历，采用DP进行优化，DP[i]表示第i个及之后的点所能组成的最大团。若当前层数为x，剩下的点从i开始，那么如果 x+DP[i]<=ans ，那么同样可以直接返回。
参考代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define N 60 int G[N][N],V[N][N]; int n,ans,dp[N]; void dfs(int deep,int num) { if(!num) { ans=deep>ans?deep:ans; return; } for(int i=1;i<=num;i++) { if(deep+1+num-i<=ans) return; int cur=V[deep][i]; if(deep+dp[cur]<=ans) return; int cnt=0; for(int j=i+1;j<=num;j++) { int nex=V[deep][j]; if(G[cur][nex]) V[deep+1][++cnt]=nex; } dfs(deep+1,cnt); } } int main() { while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&G[i][j]); } } ans=0; memset(dp,0,sizeof(dp)); for(int i=n;i;i--) { int cnt=0; for(int j=i+1;j<=n;j++) { if(G[i][j]) V[1][++cnt]=j; } dfs(1,cnt); dp[i]=ans; } cout<<ans<<endl; } }
