「日常训练」 Counting Cliques（HDU-5952）

题意与分析

题源：2016ACM/ICPC沈阳现场赛。

这题让我知道了什么是团，不过最恶心的还是这题的数据了，卡了无数次- -

解决方法是维护一个G数组，不能去遍历邻接矩阵。至少我改了这么一个地方就过了，实在找不到其他可以卡人的地方了。。。

代码

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (repType i = (a); i <= (b); ++i)

#define per(i, a, b) for (repType i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

typedef long long ll;

typedef int repType;

const int MAXN=110;

vector<int> G[MAXN];

bool mp[MAXN][MAXN];

int n, m, s;

int ans;

void

dfs(int u, int* stk, int nowdep)

{

    if(nowdep==s)

    {

        ans++; return;

    }

    rep(i, 0, int(G[u].size())-1) //可能加入团的点

    {

        int v=G[u][i];

        bool ok=true;

        rep(j, 1, nowdep) //遍历团中所有点，判断是否与将要加入的点相连

        {

            if(!mp[v][stk[j]])

            {

                ok=false;

                break;

            }

        }

        if(ok) //这个点可以加入团，加入并继续深搜

        {

            stk[++nowdep]=v;

            dfs(v, stk, nowdep);

            stk[nowdep--]=0;

        }

    }

}

int

main()

{

    int T; scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d%d", &n, &m, &s);

        rep(i, 1, n) { G[i].clear(); }

        ZERO(mp);

        ans=0;

        while(m--)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            if(u>v) { swap(u, v); }

            G[u].push_back(v);

            mp[u][v]=mp[v][u]=true;

        }

        rep(i, 1, n)

        {

            int nd=1; //团的规模

            int stk[MAXN]; //tmp集合表示这个团中有哪些点

            stk[1]=i;

            dfs(i, stk, nd);

        }

        printf("%d\n", ans);

    }

    return 0;

}