先膜拜+感謝owen，QW。

今天用了很多的時間研究了一道狀態壓縮搜索題。

求最大團的個數及方案數。

組隊（mc） 【問題描述】 小秋秋想出去玩了。。 小秋秋有許多朋友，有一些小秋秋的朋友相互之間也是朋友。。。 小秋秋覺得自己帶不是朋友的兩個朋友出去玩會出現尷尬。。。（好糾結） 小秋秋想知道自己最多可以帶多少朋友出去玩以及帶人最多的方案數。。 【輸入文件】(input.txt) 第一行兩個數，n,m 分別表示小秋秋的朋友數，以及他們之間相互認識的關 系對數。 接下來 m 行，每行兩個整數 x,y 表示朋友 x 和朋友 y 他們相互認識。 【輸出文件】(output.txt) 一行兩個整數，分別表示能選出一起出去玩得最大人數，以及能達到最大人 數的方案數。 【樣例輸入】 4 5 1 2 2 3 3 1 1 4 2 4 【樣例輸出】 3 2 【數據約定】 test 0 1 2 3 4 5 6 7 8 9 n 5 10 15 20 25 30 35 40 45 50
雖然用二分圖的知識（求最大獨立集再取反）可以比較簡單的求出最大團的個數，但是要求方案數就無能為例了。?

此題我一共寫了三個版本。

一是爆搜。QW寫了個dancing links優化

二是搜索選點組合，再利用狀態壓縮優化最大團的判斷。

三是搜索選點組合+最優化剪枝、縮小上界，再利用狀態壓縮優化最大團的判斷。

另吐槽下蒯個標程當題解發出來的童鞋。

?

注：

為便于敘述，不妨將滿足本題中要求的子圖叫做團。（實際上團的概念并非如此）

?

然后我對每個代碼里有意義部分進行下解釋吧。

code1

#include <cstdio> #include <iostream> using namespace std;const int maxn = 50 + 5;int n, m; int tmp[maxn]; int map[maxn][maxn]; int nmax(-INT_MAX), tmax(-INT_MAX);void check(int v), dfs(int u, int v);int main() {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);cin >> n >> m;for (int i = 1, x, y; i <= m; ++i)scanf("%d%d", &x, &y),map[x][y] = map[y][x] = 1;dfs(0, 0);cout << nmax << " " << tmax << endl;return 0; }void check(int v) {bool mix(1);for (int i = 1; i <= v; ++i)for (int j = i + 1; j <= v; ++j)if (!map[tmp[i]][tmp[j]]) { mix = 0; break; }if (!mix) return;if (v > nmax) nmax = v, tmax = 1;else if (v == nmax) ++tmax; }void dfs(int u, int v) {if (v >= nmax) check(v);if (u >= n || v >= n) return;for (int i = u + 1; i <= n; ++i){tmp[v + 1] = i;dfs(i, v + 1);} }

搜索沒什么好講的，而且沒狀壓= ?=。

然后 Orz cuizimu不狀態壓縮裸搜只要1 s！

code2

#include <cstdio> #include <iostream> using namespace std;const int maxn = 50 + 5;int n, m; int tmp[maxn]; int map[maxn][maxn]; long long s[maxn]; int nmax(-INT_MAX), tmax(-INT_MAX);void check(int v), dfs(int u, int v, long long sta);int main() {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);cin >> n >> m;for (int i = 1, x, y; i <= m; ++i)scanf("%d%d", &x, &y),map[x][y] = map[y][x] = 1;//預處理成二進制串for (int i = 1; i <= n; ++i){long long sta = 1;for (int j = 1; j <= n; sta <<= 1, ++j)if (map[i][j] != 0) s[i] += sta;}dfs(0, 0, 0);cout << nmax << " " << tmax << endl;return 0; }void dfs(int u, int v, long long sta) {if (u >= n) return;for (int i = u + 1; i <= n; ++i)if ((sta & s[i]) == sta){if (v + 1 > nmax) nmax = v + 1, tmax = 1;else if (v + 1 == nmax) ++tmax;dfs(i, v + 1, sta | ((long long)1 << (i - 1)));//位運算記得要強制類型轉換} }

加上狀態壓縮優化。

狀態壓縮比較易懂，開long long強壓鄰接矩陣的結果s[i]，即用一個二進制數串表示了i號點所連接的點，能直接相連則為1，不能直接相連則為0。如若2能與3, 4, 7, 8號點相連，則狀態壓縮后表示為 s[2] = 11001100 。

若當前狀態（已經是團但不一定最大）為sta，若(sta & s[i]) == sta，則表示加入i點后仍能維護團的性質。然后將i點加入狀態再繼續搜索即可，sta | (1 << (i- 1))。記得位運算要強制類型轉換！

code3

#include <cstdio> #include <iostream> using namespace std;const int maxn = 50 + 5;int n, m, nmax, tmax; int num[maxn], map[maxn][maxn]; long long s[maxn];void dfs(int u, int v, long long sta);int main() {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);cin >> n >> m;for (int i = 1, x, y; i <= m; ++i)scanf("%d%d", &x, &y),map[x][y] = map[y][x] = 1;//預處理成二進制串for (int i = 1; i <= n; ++i){long long sta = 1;for (int j = 1; j <= n; sta <<= 1, ++j)if (map[i][j] != 0) s[i] += sta;}for (int i = n; i >= 1; --i){dfs(i, 0 + 1, 0 | (1LL << (i - 1)));num[i] = nmax;}cout << nmax << " " << tmax << endl;return 0; }void dfs(int u, int v, long long sta) {if (u >= n) return;for (int i = u + 1; i <= n - nmax + v + 1; ++i)//縮小上界 if ((sta & s[i]) == sta){if (v + 1 > nmax) nmax = v + 1, tmax = 1;else if (v + 1 == nmax) ++tmax;if (v + 1 + num[i] < nmax) continue;dfs(i, v + 1, sta | (1LL << (i - 1)));//位運算記得要強制類型轉換前面的數} }

此代碼寫法與前兩個感覺已經有本質區別了。

首先主程序中最開始是由n~1開始搜索的，每次搜索最開始的i必須選，目的是可以用第一個很強的最優性剪枝。

有些公式沒法放進CSDN blog于是我就截圖了

code3效率是不錯的（0.5s）

但由于最初我是從 n~1 枚舉的，因此有一個同樣很強的優化用不上

但我提供下標程給讀者思考吧

#include<cstdio> long long e[55]; int f[55],n,m,i,j,k,s,ans,max; void up(int x) {if (x == max) ans++;else max = x, ans = 1; } void dfs(int x,int s,long long V,long long E) {if ((V & E) != V || s + f[x] < max) return;if (x > n) { up(s); return; };dfs(x + 1, s + 1, V |(1LL << x - 1), E & (e[x]));dfs(x + 1, s, V, E); } int main() {freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);scanf("%d%d",&n,&m);for (; m; m--)scanf("%d%d", &i, &j), e[i] |= 1LL << j - 1, e[j] |= 1LL << i - 1;for (i = 1; i <= n; i++) e[i] |= 1LL << i - 1;for (i = n; i; i--){dfs(i+1, 1, 1LL << i - 1, e[i]);f[i] = max;}printf("%d %d", max, ans);return 0; }

總結

以上是生活随笔為你收集整理的最大团的求法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。