极大团个数模板

感觉很玄学
套用就对了orz
上代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 130
using namespace std;

int p[maxn][maxn],r[maxn][maxn],x[maxn][maxn];//p 代表还没加的点 r 代表已加入的点 x代表已经完成计数的点
int ans=0;
int a[maxn][maxn];

int n,m;
bool find(int d,int nr,int np,int nx){ //d代表第n个点 nr代表加入点的数量 np代表还没加入点的数量 nx代表已经完成计数的数量
//int i,j;
if(np==0&&nx==0){ //如果 p已经没了并且x也没了那么就可以取到一种条件
ans++;
if(ans>1000) return 1; //假如ans已经大于1000了直接退回
return 0;
}
int u,maxx=0;
u=p[d][1]; //令 u=1

for(int i=1;i<=np;i++){ //这个操作是为了找一个最大的u点 使后续遍历更少 算一个优化~~
int cnt=0;
for(int j=1;j<=np;j++){
if(a[p[d][i]][p[d][j]]) cnt++;
}
if(cnt>maxx){
maxx=cnt;
u=p[d][i];
}
}

for(int i=1;i<=np;i++){
int v=p[d][i]; //从还没加过的点开始找
if(a[v][u]) continue;
for(int j=1;j<=nr;j++){ //将点v加入集合r(已加入的点的集合)
r[d+1][j]=r[d][j];
}
r[d+1][1+nr]=v;
int cnt1=0;
for(int j=1;j<=np;j++){ //取v与p相交的部分
if(p[d][j]&&a[p[d][j]][v])
p[d+1][++cnt1]=p[d][j];
}
int cnt2=0;
for(int j=1;j<=nx;j++){ //取v与x相交的部分
if(a[x[d][j]][v])
x[d+1][++cnt2]=x[d][j];
}
if(find(d+1,nr+1,cnt1,cnt2)) return 1;
p[d][i]=0;
x[d][++nx]=v; //将v加入x集合
}
return 0;
}


int main(){
while(~scanf("%d%d",&n,&m)){
memset(a,0,sizeof a);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
ans=0;
for(int i=1;i<=n;i++) p[1][i]=i;
find(1,0,n,0);
if(ans>1000) printf("Too many maximal sets of friends.\n");
else printf("%d\n",ans);
}
return 0;
}

我们知道在上述的算法中必然有许多重复计算之前计算过的极大团然后调出的过程。
然后我们考虑如下问题,取集合P ∪X中的一个点u,要与R集合构成极大团,那么取得点必然是P \ N(u)中一个一个点 N(u)代表P中是u邻居的点,
通俗的来讲取的点要么是u,要么就是与u不相邻的点,这样我们照样可以重复不漏的计算所有极大团,这个的正确性十分好想,就不证明了,也可以参照wiki中的解释,
然后我们每次取从原先的遍历P中所有点变成了遍历P中u点与不与u相邻的点即P \ N(u),这样我们可以减少许多不必要的计算,而我们要想进一步减少计算,我们就可以取u,
使得u的邻居最多,也就是使我们要遍历的点进一步减少

最后更新: 2019年05月30日 21:31

原始链接: http://yoursite.com/2019/05/02/极大团模板/

× 请我吃糖~
打赏二维码