现在的位置: 首页 > 综合 > 正文

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

2018年12月23日 ⁄ 综合 ⁄ 共 835字 ⁄ 字号 评论关闭

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;
}

抱歉!评论已关闭.