传送门：HDU5952
题意：给出一个无向图，问其中点集大小为S的无向完全子图的个数。
思路：就是暴搜，但是建图有技巧，因为搜索过程中很容易出现重复序列，比如我们第一次搜到的答案是1 2 3，下一次搜到的是1 3 2，这两个实际上是同一种子图，搜索这些无用状态既浪费时间，去重还很麻烦。技巧就是建图的时候建成有向图，只让标号小的顶点指向标号大的顶点，这样搜出来的序列一定是一个 v1 < v2 < v3 。。。这样的偏序序列，既避免了重复，又节省了大量的时间。
代码：
#include<bits/stdc++.h> #define ll long long #define pb push_back #define fi first #define se second #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define rep(i,x,n) for(int i=x;i<n;i++) #define per(i,n,x) for(int i=n;i>=x;i--) using namespace std; typedef pair<int,int>P; const int MAXN=100010; int gcd(int a,int b){return b?gcd(b,a%b):a;} int g[110][110]; vector<int> e[110]; int t[110]; int ans, S; void dfs(int u, int cnt) { if(cnt == S) { //for(int i = 0; i < cnt; i++) //cout << t[i] << " "; //cout << endl; ans++; return ; } int sz = e[u].size(); for(int i = 0; i < sz; i++) { int v = e[u][i], flag = 0; for(int j = 0; j < cnt; j++) { if(!g[v][t[j]]) { flag = 1; break; } } if(flag) continue; t[cnt] = v; dfs(v, cnt + 1); t[cnt] = 0; } } int main() { int T, n, m, v, u; cin >> T; while(T--) { ans = 0; memset(g, 0, sizeof(g)); scanf("%d %d %d", &n, &m, &S); for(int i = 0; i < m; i++) { scanf("%d %d", &u, &v); if(u > v) swap(u, v); e[u].pb(v); g[u][v] = g[v][u] = 1; } for(int i = 1; i <= n; i++) { t[0] = i; dfs(i, 1); } cout << ans << endl; for(int i = 1; i <= n; i++) e[i].clear(); } return 0; }
