hdu1530 求最大团

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1530

求最大团裸题。

模板：maxx即为所求的最大团的值。

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int mp[][],mark1[],mark2[];

int n,cnt,maxx;

void dfs(int x)

{

    if(x>n)   // 如果枚举了所有的节点

    {

        maxx=cnt;

        memcpy(mark1,mark2,sizeof(mark2)); // 用一个更大的极大团替代原有的极大团

        return;

    }

    int flag=true;

    for(int i=; i<x; i++)   // 检测新加入的点是否到团中的其他节点都存在一条边

    {

        if(mark2[i] && !mp[i][x])

        {

            flag=false;

            break;

        }

    }

    if(flag)   // 如果该节点满足在这个团中

    {

        mark2[x]=,cnt++; // 该节点被加入到完全子图中去

        dfs(x+);

        mark2[x]=,cnt--;

    }

    if (cnt+n-x>maxx)   // 跳过x节点进行搜索同时进行一个可行性判定

        dfs(x+);

}

int main()

{

    while(scanf("%d",&n)== && n)

    {

        memset(mark1,,sizeof(mark2));

        memset(mark2,,sizeof(mark2));

        maxx=cnt=;

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

            for(int j=; j<=n; j++)

                scanf("%d",&mp[i][j]);

        dfs();

        printf("%d\n",maxx);

    }

    return ;

}

代码1：

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int n;

int mp[][],mark[];

int cn,maxx;

//没优化，跑9000+msvoid dfs(int x)  //dfs(1);

{

    if(x>n)

    {

        maxx=cn;

        return;

    }

    int flag=;

    for(int i=; i<x; i++)

    {

        if(mark[i]&&!mp[x][i])

        {

            flag=;

            break;

        }

    }

    if(flag)

    {

        cn++;

        mark[x]=;

        dfs(x+);

        cn--;

    }

    if(cn+n-x+>maxx)  ///这句话看了好久都没懂是什么意思

    {

        mark[x]=;

        dfs(x+);

    }

}

int main()

{

    while(scanf("%d",&n)== && n)

    {

        memset(mp,,sizeof(mp));

        memset(mark,,sizeof(mark));

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

            for(int j=; j<=n; j++)

                scanf("%d",&mp[i][j]);

        cn=maxx=;

        dfs();

        printf("%d\n",maxx);

    }

    return ;

}

代码2：

#include<cstdio>

#include<cstring>

const int N=;

//最大团模板

bool a[N][N];//a为图的邻接表(从1开始)

int cnt[N],group[N],vis[N];//cnt[N]表示当前最大团的节点数，group[N]用以寻找一个最大团集合

int n,m,ans;//ans表示最大团

//dfs(i,1);

bool dfs(int u,int pos)//u为当从前顶点开始深搜，pos为深搜深度（即当前深搜树所在第几层的位置）

{

    int i,j;

    for(i=u+; i<=n; i++)//按递增顺序枚举顶点

    {

        if(cnt[i]+pos<=ans) return ;//剪枝

        if(a[u][i])

        {

            //与目前团中元素比较，取 Non-N(i)

            for(j=; j<pos; j++)

                if(!a[i][vis[j]])

                    break;

            if(j==pos)

            {

                //若为空，则皆与 i 相邻，则此时将i加入到 最大团中

                vis[pos]=i;//深搜层次也就是最大团的顶点数目，vis[pos]=i表示当前第pos小的最大团元素为i（因为是按增顺序枚举顶点 ）

                if(dfs(i, pos+)) return ;

            }

        }

    }

    if(pos>ans)

    {

        for(i=; i<pos; i++)

            group[i]=vis[i]; // 更新最大团元素

        ans=pos;

        return ;

    }

    return ;

}

void maxclique()//求最大团

{

    ans=-;

    for(int i=n; i>; i--)

    {

        vis[]=i;

        dfs(i,);

        cnt[i]=ans;

    }

}

int main()

{

    while(scanf("%d",&n)== && n)

    {

        if(n==) break;

        int x,y;

        memset(a,,sizeof(a));

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

            for(int j=; j<=n; j++)

                scanf("%d",&a[i][j]);

        maxclique();

        if(ans<) ans=;//ans表示最大团

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

    }

}

代码3：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,path[][],s[],dp[],ans;

bool is_clique(const int ed,const int point)

{

    for(int i=; i<ed; i++)

        if(!path[s[i]][point]) return false;

    return true;

}

void dfs(int depth,int now)

{

    if(depth+n-now+<=ans||depth+dp[now]<=ans) return;

    for(int i=now; i<=n; i++)

    {

        if(is_clique(depth+,i))

        {

            s[depth+]=i;

            dfs(depth+,i+);

        }

    }

    if(depth>ans) ans=depth;

}

int main()

{

    while(scanf("%d",&n)== && n)

    {

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

            for(int j=; j<=n; j++)

                scanf("%d",&path[i][j]);

        memset(dp,,sizeof(dp));

        ans=;

        dp[n]=;

        for(int i=n-; i>=; i--)

        {

            s[]=i;

            dfs(,i+);

            dp[i]=ans;

        }

        printf("%d\n",dp[]);

    }

    return ;

}