感觉很玄学
套用就对了 orz
上代码
- #include
- #include
- #include
- #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("%dn",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 的邻居最多, 也就是使我们要遍历的点进一步减少
极大团模板
来源: http://www.bubuko.com/infodetail-3320021.html