听了Yasola瞎逼逼打算去搞一下那些很混乱的东西。
首先就是这个最大团问题

建议先点开看看上面的百度百科链接。虽然东西很多,我也只是浏览了一下

瞎逼逼与个人理解

首先必须强调的是最大团是一个NP-Hard问题,目前并没有一个合适的在多项式时间内完美求得正解的算法。

而Bron–Kerbosch算法,名字好像是非常吊,其实就是各种优化过的搜索算法。
学习博客点这里

简单说一下个人理解。

Bron–Kerbosch算法基于基本搜索,但优化之处很多,优化有如下

  1. 比较常见的指定顺序搜索,避免重复
  2. 对于当前深度 dep , 如果剩余点数与之相加都不能更新 ans ,就剪枝
  3. dp 优化,用dp记录之前搜索得到的最大团数量,如无法更新ans,剪枝。

下面有两个入门 板子

HDU 1530 Maximum Clique

题意:
最大团的裸题。给你邻接矩阵,让你求最大团的点数。

思路:
套一套模板就行啦……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
//#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 55;

int n, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    ans = max(dep, ans);
}

int main()
{
    while (~scanf("%d", &n) && n) {
        range(i, 1, n) range(j, 1, n) scanf("%d", &g[i][j]);
        fill(dp, dp + n + 1, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
    }
    return 0;
}

POJ 1419 Graph Coloring

题意:
给你一些边,让你求最大独立集。

思路:
无向图的最大独立集 = 补图的最大团。
因此建立补图,跑一遍即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 105;

int n, m, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn], avex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    if (ans < dep) {
        ans = dep;
        memcpy(avex, vex, sizeof vex);
    }
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, n) range(j, 1, n) g[i][j] = 1;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = 0;
        }
        fill(dp, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
        range(i, 1, ans) printf("%d%c", avex[i], " \n"[i == ans]);
    }
    return 0;
}
Categories: 最大团

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最大团

HDU 5556 Land of Farms 附最大团最终模板

一眼以为是状压DP…… 但是仔细读题的话,会有一个致命条件是状压无法解 Read more…

最大团

HDU 3585 maximum shortest distance

淦啊……我之前自以为入门的最大团DP优化板子是错的,我说怎么和极大团计 Read more…

最大团

POJ 2989 All Friends

最大团问题之极大团计数。 啊呀啊呀,基本都会是板子题啦…… 但是尽管是 Read more…