POJ 2989 All Friends

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

啊呀啊呀，基本都会是板子题啦……
但是尽管是板子题，上次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;
}