注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

最大团算法  

2014-06-26 12:34:19|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

以下算法属于转载:


首先,我们先得到后几个点组成的最大团到底是多大,(最开始的时候肯定是最后一个点单独构成一个最大团,点数为1)然后我们再 DFS:

    初始化:

      从一个点 u 开始,把这个点加入集合 U 中。将编号比它大的且和它相连的点加入集合 S1 中,为了方便,将集合 S1 中的点有序,让他们从小到大排列,进行第一遍 DFS

    第一遍 DFS :

      从 S1 中选择一个点 u1,遍历 S1 中,所有编号比 u1 大且和 u1 相连的点,其实也就是排在 u1 后面,并且和 u1 相连的点,将它们加入集合 S2 中。同理,让 S2 中的点也按照编号也从小到大排列。将 u1 加入集合 U 中,进行第二遍 DFS

    第二遍 DFS :

      从 S2 中选择一个点 u2,遍历 S2 中,所有排在 u2 后面且和 u2 相连的点,并把它们加入集合 S3 中,让 S3 中的点按照编号从小到大排列,将 u2 加入集合 U 中进行第三遍 DFS

    第三遍 DFS :

      从 S3 中选择一个点 u3,遍历 S3 中,所有排在 u3 后面且和 u3 相连的点,并把它们加入集合 S4 中,让 S4 中的点按照编号从小到大排列,将 u3 加入集合 U 中进行第四遍 DFS

    ......

    最底层的 DFS :

      当某个 S 集合为空时,DFS 过程结束,得到一个只用后面几个点构成的完全子图,并用它去更新只用后面几个点构成的最大团。退出当前 DFS,返回上层 DFS,接着找下一个完全子图,直到找完所有的完全子图

 

上面的 DFS 过程,如果不加任何剪枝的话,其实和第一个 DFS 是差不多的,但是既然我们都这样 DFS 了,能不能想一想怎么剪枝呢?

假设我们当前处于第 i 层 DFS,现在需要从 Si 中选择一个 ui,把在 Si 集合中排在 ui 后面的和 ui 相连的点加入集合 S(i+1) 中,把 ui 加到集合 U 中

可能大家稍作思考之后就想到了一个剪枝:

 

剪枝1:如果 U 集合中的点的数量+1(选择 ui 加入 U 集合中)+Si 中所有 ui 后面的点的数量  当前最优值,不用再 DFS 了

 

还有什么剪枝呢?

注意到我们是从后往前选择 u 的,也就是说,我们在 DFS 初始化的时候,假设选择的是编号为 x 的点,那么我们肯定已经知道了用 [x+1, n] ,[x+2, n],[x+3, n] ...[n,n] 这些区间中的点能构成的最大团的数量是多大

 

剪枝2:如果 U 集合中的点的数量+1(理由同上)+[ui, n]这个区间中能构成的最大团的顶点数量  当前最优值,不用再 DFS了

 

有这两个剪枝就够了吗?

不,我们还能想出一个剪枝来:

 

剪枝3:如果 DFS 到最底层,我们能够更新答案,不用再 DFS 了,结束整个 DFS 过程,也不再返回上一层继续 DFS 了

 

为什么?因为我们如果再继续往后 DFS 的话,点的编号变大了,可用的点变少了(可用的点在一开始 DFS 初始化的时候就确定了,随着不断的加深 DFS 的层数,可用的点在不断的减少)

 

有了上面三个剪枝,100 个点以内的图,我们也能非常快的出解了

 

可能有人会问,如果想知道最大团包含哪些节点该怎么办?

这还不简单?每次 DFS 都会加一个点进入 U 集合中,DFS 到最底层,更新最大团数量的时候,U 集合中的点一定是一个完全子图中的点集,用 U 集合更新最大团的点集就行了

 

三、常用结论

 

1、最大团点的数量=补图中最大独立集点的数量

2、二分图中,最大独立集点的数量+最小覆盖点的数量=整个图点的数量

3、二分图中,最小覆盖点的数量=最大匹配的数量

4、图的染色问题中,最少需要的颜色的数量=最大团点的数量


bzoj3632

模板题:

#include<cstdio>
#define nn 60
using namespace std;
int ans,n,i,a,b,j,flo[nn][nn],f[nn];
bool g[nn][nn];
bool DFS(int cur,int tem)
 {int i,u,suf;
 if (!cur)
  {if (tem>ans)
   {ans=tem;
    return true;
   }
   return false;
  }
 for (i=1;i<=cur;i++)
  {if (tem+cur-i+1<=ans)
   return false;
   u=flo[tem][i];
   if (f[u]+tem<=ans)
   return false;
   suf=0;
   for (j=i+1;j<=cur;j++)
    if (g[u][flo[tem][j]])
         flo[tem+1][++suf]=flo[tem][j];
   if (DFS(suf,tem+1))return true;
  }
 return false;
 }
int maxclique()
 {int i,j,cur;
 for (i=n;i>=1;i--)
  {cur=0;
   for (j=i+1;j<=n;j++)
     if (g[i][j])
        flo[1][++cur]=j;
   DFS(cur,1);
   f[i]=ans;
  }
 return ans;
 }
int main()
{
 scanf("%d",&n);
 while (scanf("%d%d",&a,&b)!=EOF){
     g[a][b]=g[b][a]=true;
 }
printf("%d\n",maxclique());
return 0;
}

?

  评论这张
 
阅读(6431)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018