最大团问题之极大团计数。

啊呀啊呀,基本都会是板子题啦……
但是尽管是板子题,上次ccpc网络赛卡我的题,我当时要是有个最大团的板子,就可以直接过了……

极大团计数和最大团不大一样,这里有wiki上的伪代码

BronKerbosch(All, Some, None):
if Some and None are both empty:
report All as a maximal clique //所有点已选完,且没有不能选的点,累加答案
for each vertex v in Some: //枚举Some中的每一个元素
BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))
//将v加入All,显然只有与v为朋友的人才能作为备选,None中也只有与v为朋友的才会对接下来造成影响
Some := Some - {v} //已经搜过,在Some中删除,加入None
None := None ⋃ {v}

其实就是一个优化过的回溯算法……最大团是NP问题,没办法,过几天会去学一下随机化吧。

题意:
极大团计数裸题,给你n个点,m条边,问你极大团数量。

思路:
具体看上面的伪代码。

值得注意的是,使用板子的时候格外要注意,边界外的邻接矩阵不能设置为 true ,不然会出错。不具体解释。

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 = 130;

int ans;
bool g[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn];
int all[maxn][maxn];

void dfs(int cur, int sz, int sn, int nn)
{
    if (!sn && !nn)
        ans++;
    if (ans > 1000)
        return;
    int key = some[cur][1];
    range(i, 1, sn)
    {
        int v = some[cur][i], tsn = 0, tnn = 0;
        if (g[key][v])
            continue;
        range(j, 1, sz) all[cur + 1][j] = all[cur][j];
        all[cur + 1][sz + 1] = v;
        range(j, 1, sn) if (g[v][some[cur][j]]) some[cur + 1][++tsn] = some[cur][j];
        range(j, 1, nn) if (g[v][none[cur][j]]) none[cur + 1][++tnn] = none[cur][j];
        dfs(cur + 1, sz + 1, tsn, tnn);
        some[cur][i] = 0, none[cur][++nn] = v;
    }
}

int main()
{
    int u, v, n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        fill(g, false), ans = 0;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = true;
        }
        range(i, 1, n) some[1][i] = i;
        dfs(1, 0, n, 0);
        if (ans > 1000)
            puts("Too many maximal sets of friends.");
        else
            printf("%d\n", ans);
    }
    return 0;
}
Categories: 最大团

发表评论

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

Related Posts

最大团

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

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

最大团

HDU 3585 maximum shortest distance

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

最大团

最大团Bron–Kerbosch算法入门

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