题目来源

hdu 1530 Maximum Clique

题目描述

给定一个图G(V,E)，让你求最大完全子图(最大团)。

输入

输入包含多个测试。对于每个测试： 第一行有一个整数n，即顶点数。 （1 <n <= 50） 接下来的n行分别具有n 0或1，表示在i（行号）和j（列号）之间是否存在边。 n = 0的测试表示输入结束。

输出

输出最大团中的顶点数目。

样例输入

5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0

样例输出

4

//最大团问题 hdu.1530

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int g[N][N],n,ans,res[N];
int f[N]; //f[i]表示从i到n-1挑最多的最大团点数
bool dfs(int tot,int may[],int mayc)
{
    if(!mayc)
    {
        if(tot>ans)
        {
            ans=tot;
            return 1;
        }
        return 0;
    }

    for(int i=0;i<mayc;i++)
    {
        int u=may[i];
        if(tot+n-u<=ans) return 0;
        if(tot+f[u]<=ans) return 0;

        int nmay[N],nmayc=0;
        for(int j=i+1;j<mayc;j++) if(g[u][may[j]]) nmay[nmayc++]=may[j];

        if(dfs(tot+1,nmay,nmayc)) return 1; //能更新说明能完成比ans多1的任务了，就不用往下走了，应为再走下去也只能多1.
    }

    return 0;
}
int main()
{
    while(cin>>n,n)
    {
        memset(f,0,sizeof f);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&g[i][j]);
        ans=1;
        for(int i=n-1;i>=0;i--)
        {
            res[0]=i;
            int may[N],mayc=0;
            for(int j=i+1;j<n;j++)  if(g[i][j]) may[mayc++]=j;
            dfs(1,may,mayc);
            f[i]=ans;
        }
        cout<<f[0]<<endl;
    }
    return 0;
}