hdu1530 Maximum Clique,最大团 ， DP，邻接矩阵

Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxv = 60;
int g[maxv][maxv], dp[maxv], stk[maxv][maxv], mx;
int dfs(int n, int ns, int dep)
{
    if (0 == ns) {
        if (dep > mx) mx = dep;
        return 1;
    }
    int i, j, k, p, cnt;
    for (i = 0; i < ns; i++) {
        k = stk[dep][i];
        cnt = 0;
        if (dep + n - k <= mx) return 0;
        if (dep + dp[k] <= mx) return 0;
        for (j = i + 1; j < ns; j++) {
            p = stk[dep][j];
            if (g[k][p]) stk[dep + 1][cnt++] = p;
        }
        dfs(n, cnt, dep + 1);
    }
    return 1;
}
int clique(int n)
{
    int i, j, ns;
    for (mx = 0, i = n - 1; i >= 0; i--) {
    // vertex: 0 ~ n-1
        for (ns = 0, j = i + 1; j < n; j++)
            if (g[i][j]) stk[1][ ns++ ] = j;
        dfs(n, ns, 1);
        dp[i] = mx;
    }
    return mx;
}
int main()
{
    int n;
    while(~scanf("%d", &n),n) {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                scanf("%d", &g[i][j]);
        int ans = clique(n);
        printf("%d\n", ans);
    }
    return 0;
}

hdu1530 Maximum Clique,最大团 ， DP，邻接矩阵

原文：http://blog.csdn.net/yew1eb/article/details/39201879