zju 1492

2009年8月11日

题目链接：ZJU 1492 Maximum Clique

分类：典型的NP问题之最大团

题目分析与算法原型
         这是一个最大团问题，老实说，这道题已经TLE了好多次，之后由于细节上的一个错误又WA了几次（TLE就算了，还WA了，真有必要BS下自己），先前简直就是直接暴力DFS，然后才发现这题不愧是NP问题，10秒的限时都被我超了（看来这种问题还是不能有侥幸心理，orz......）
        当然这题也是可以在我原先的想法上减枝的，我原先的想法是从0开始一直到n-1枚举每个点进行一次dfs,因为问题求的是最大的完全子图的顶点数，所以，我每加进来一个点，枚举和其相邻的点x，判断下x是否和已经加近来的点（用一个数组记录当前已经找到的最大的完全图的各个顶点编号）都有边，当且仅当和里面所有的点都有边时候才把x加入.........思路是比较清晰，但是这复杂度简直不可想象，其实有个比较好的方法（小Q同学的提醒），从n-1到0枚举每个点，保存一个数组cnt[],其中cnt[i]记录的是从顶点i一直到n-1这些点中找到的完全图的最大顶点数（那么原问题就是求cnt[0]），到这里那么我们可以发现cnt[i-1]=cnt[i]或者cnt[i]+1，这一步的发现很重要，因为是一个很有力的减枝，每次从传入的顶点编号num的下个num+1到n-1找与num相邻的点，设当前枚举的是i,若当前找到的完全图的顶点数+cnt[i]<=max（max为现在找到的所有完全图的最大顶点数）那么直接返回false，因为cnt[]数组是非递增的，所有以后的都可以不用考虑了，还有根据cnt数组的这一个非递增的特性，一旦某次更新了max，也就可以直接返回true了..........

Code: 

 1#include<stdio.h>
 2#include<string.h>
 3#define len 55
 4int map[len][len],n,max,cnt[len];
 5bool dfs(int num,int visit[len],int pos)
 6{
 7    int i,j;
 8    for(i=num+1;i<n;i++)
 9    {
10        if(cnt[i]+pos<=max) return false;
11        if(map[num][i])
12        {
13            for(j=0;j<pos;j++)if(map[i][visit[j]]==0)break ;
14            if(j==pos)
15            {
16               visit[pos]=i;
17               if(dfs(i,visit,pos+1))return true;
18            }
19        }
20    }
21    if(pos>max)
22    {
23        max=pos;
24        return true;
25    }
26    return false;
27}
28int main()
29{
30    while(scanf("%d",&n)!=EOF&&n)
31    {
32        int i,j,path[len];
33        for(i=0;i<n;i++)
34            for(j=0;j<n;j++)scanf("%d",&map[i][j]);
35            max=-1;
36            for(i=n-1;i>=0;i--)
37            {
38                path[0]=i;
39                dfs(i,path,1);
40                cnt[i]=max; 
41            }
42            printf("%d\n",cnt[0]);
43    }
44    return 1;
45}

posted on 2009-08-11 18:01 蜗牛也Coding 阅读(531) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜