POJ 2989 All Friends 极大团计数

POJ 2989

题意：给定一个无向图（节点数小于128）求极大团（不包含在更大的团中）的总数。

对最大团，极大团不熟悉的，建议先阅读最大团搜索问题 ZOJ 1492 再来看本题。

本题数据有限，可以使用dfs解决。类似于搜索最大团的加强版。有“两个”剪枝需要注意。

在dfs中需要维护两个集合即 Not(已经尝试过搜索极大团的节点)和Candidate（未曾尝试过的节点）由于极大团带有集合的性质，故某个节点在dfs序列中出现的位次并不重要。

当Not和Can集合同时为空时结束dfs。

在代码中，Not节点集合用ne数组标记，Can节点集合用ce数组标记

剪枝1：若当前Not集合中存在一个点，与Can中所有点都相连，则在未来的搜索中它永远不会离开Not集合，故剪枝。

剪枝2：这个剪枝为了优化剪枝1的效果，并不是一个新的剪枝。

　　　　原本的搜索我们总是从Can集合中随意选择一个继续dfs 但是我们可以挑选一个特殊的节点，来增强剪枝1的效果。

设每个在Not集合中的节点有一个cnt值，为Can集合中与它不相连的节点个数。

我们于是选择Can集合中与cnt最小的节点不相连的节点进行下一步dfs。

代码如下

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=130;

int n,m,ans,ne[maxn],ce[maxn],list[maxn][maxn];

bool g[maxn][maxn];

void dfs(int size)

{

 if(ans>1000)return ;

 int i,j,k,t,cnt,best=0;

 if(ne[size]==ce[size])

 	{

 	 if(ce[size]==0)++ans;

 	 return ;

	}

 for(t=0,i=1;i<=ne[size];++i)

 	{

 	 for(cnt=0,j=ne[size]+1;j<=ce[size];++j)

 	 	if(!g[list[size][i]][list[size][j]])++cnt;

 	 if(t==0||cnt<best)t=i,best=cnt;

	}

 if(t&&best<=0)return ;//剪枝1

 for(k=ne[size]+1;k<=ce[size];++k)

 	{

 	 if(t>0)

 	 	{

 	 	 for(i=k;i<=ce[size];++i)

 	 	 	if(!g[list[size][t]][list[size][i]])break;

 	 	 swap(list[size][k],list[size][i]);//最大化剪枝1

		}

	 i=list[size][k];

	 ne[size+1]=ce[size+1]=0;

	 for(j=1;j<k;++j)

	 	if(g[i][list[size][j]])

	 		list[size+1][++ne[size+1]]=list[size][j];

	 for(ce[size+1]=ne[size+1],j=k+1;j<=ce[size];++j)

	 	if(g[i][list[size][j]])

	 	  list[size+1][++ce[size+1]]=list[size][j];

	 dfs(size+1);

	 if(ans>1000)return ;

	 ++ne[size];

	 --best;

	 for(j=k+1,cnt=0;j<=ce[size];++j)

	 	if(!g[i][list[size][j]])

	 		++cnt;

	 if(t==0||cnt<best)t=k,best=cnt;

	 if(t&&best<=0)break;

	}

}

void  cluster_count()

{

 int i;

 ne[0]=0;ce[0]=0;

 for(i=1;i<=n;++i)

    list[0][++ce[0]]=i;

 ans=0;

 dfs(0);

}

int main()

{

 while(scanf("%d%d",&n,&m)!=EOF)

 	{

 	 memset(g,0,sizeof(g));

 	 for(int i=0;i<m;i++)

 	 	{

 	 	 int a,b;

 	 	 scanf("%d%d",&a,&b);

 	 	 g[a][b]=g[b][a]=true;

		}

	 cluster_count();

	 if(ans>1000)printf("Too many maximal sets of friends.\n");

	 	else printf("%d\n",ans);

 	}

 return 0;

}

巴特西

POJ 2989 All Friends 极大团计数

最新文章

热门文章