立个flag——寒假回家之前，一天至少一个算法。

预备知识

完全子图：给定无向图$G=(V,E)$,其中$V$是节点集，E是边集。$G’=(V’,E’)$如果节点集$V’\subseteq V$,边集$E’\subseteq E$,且$G’$中任意两个节点有边相连，则称$G’$是$G$的完全子图。

团：$G$的完全子图$G’$是$G$的团，当且仅当$G’$不包含在$G$的更大的完全子图中，也就是说$G’$是$G$的极大完全子图。

最大团：$G$的最大团是指$G$的所有团中，含节点最多的团。

dfs解法

对于一个n个节点的图，最优解为一个n维0-1向量，表示对应节点是否在最大团中。于是我们就构造这么一棵子集树，深度为n，其中包含了所有可能的情况，即$2^{n+1}-1$种。

• 约束条件

假设当前扩展节点处于解空间树的第t层，那么从第一个节点到第t-1个节点的状态（是否在团里）已经确定，接下来沿着扩展节点的左分支进行扩展，此时需要判断是否将第t个节点放入团里。只要第t个节点与前t-1个节点被选中的节点（在团里的那些节点）均有边相连，则能放入团里，即$x[t]=1$；否则，就不能放入团里，即$x[t]=0$。

• 限界条件

假设当前扩展节点处于解空间树的第t层，那么从第一个节点到第t-1个节点的状态（是否在团里）已经确定。接下来要确定第t个节点的状态，无论沿哪个方向进行扩展，第t个节点的状态就确定了。那么，从第t+1个节点到第n个节点的状态还不确定。这样，可以根据前t个节点的状态确定当前已放入团里的节点个数（用cn表示），假象从第t+1个节点到第n个节点全部放入团里，放入的节点个数（用fn表示）$fn=n-t$,则$cn+fn$是所有从根出发的路径中前t-1个状态如上相同的可行解所包含的节点个数的上界。

如果$cn+fn$小于或等于当前最优解包含的节点个数bestn，则说明不需要再向子孙节点搜索。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//hdu 1530 AC代码
#include<bits/stdc++.h>

using namespace std;

const int N = 55;

int n;//图中的点数
int bestn;//最优解
int a[N][N];//图用邻接表表示
int cn;//当前已放入团中节点数量
bool x[N];//是否将第i个节点加入团中
bool bestx[N];//记录最优解

bool can_join(int t){//判断是否可以把节点t放入团中
	bool can=true;
	for(int i=1;i<t;i++){
		if(x[i]&&a[t][i]==0){//x[i]表示i是被选中的节点，a[t][i]==0表示t和j没有边相连
			can=false;
			break;
		}
	}
	return can;
}

void dfs(int t){
	if(t>n){//到达叶子节点
		for(int i=1;i<=n;i++){
			bestx[i]=x[i];
		}
		bestn=cn;
		return;
	}
	if(can_join(t)){//满足约束条件，进入左子树，即把节点t加入团
		x[t]=1;
		cn++;
		dfs(t+1);
		cn--;
	}
	if(cn+n-t>bestn){//满足限界条件，进入右子树
		x[t]=0;
		dfs(t+1);
	}
}

int main(){
	ios_base::sync_with_stdio(false);//关同步
	while(cin>>n,n){
		for(int i=1;i<=n;i++){//下标从1开始
			for(int j=1;j<=n;j++){
				cin>>a[i][j];//输入邻接表
			}
		}
		bestn=0;//初始化
		cn=0;
		dfs(1);//从第一个节点开始
		cout<<bestn<<endl;
	}
}

本文链接：
https://luojinrong.github.io/2019/01/10/最大团/