先膜拜+感謝owen，QW。

今天用了很多的時(shí)間研究了一道狀態(tài)壓縮搜索題。

求最大團(tuán)的個(gè)數(shù)及方案數(shù)。

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

此題我一共寫(xiě)了三個(gè)版本。

一是爆搜。QW寫(xiě)了個(gè)dancing links優(yōu)化

二是搜索選點(diǎn)組合，再利用狀態(tài)壓縮優(yōu)化最大團(tuán)的判斷。

三是搜索選點(diǎn)組合+最優(yōu)化剪枝、縮小上界，再利用狀態(tài)壓縮優(yōu)化最大團(tuán)的判斷。

另吐槽下蒯個(gè)標(biāo)程當(dāng)題解發(fā)出來(lái)的童鞋。

?

注：

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

?

然后我對(duì)每個(gè)代碼里有意義部分進(jìn)行下解釋吧。

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);} }

搜索沒(méi)什么好講的，而且沒(méi)狀壓= ?=。

然后 Orz cuizimu不狀態(tài)壓縮裸搜只要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;//預(yù)處理成二進(jìn)制串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)));//位運(yùn)算記得要強(qiáng)制類型轉(zhuǎn)換} }

加上狀態(tài)壓縮優(yōu)化。

狀態(tài)壓縮比較易懂，開(kāi)long long強(qiáng)壓鄰接矩陣的結(jié)果s[i]，即用一個(gè)二進(jìn)制數(shù)串表示了i號(hào)點(diǎn)所連接的點(diǎn)，能直接相連則為1，不能直接相連則為0。如若2能與3, 4, 7, 8號(hào)點(diǎn)相連，則狀態(tài)壓縮后表示為 s[2] = 11001100 。

若當(dāng)前狀態(tài)（已經(jīng)是團(tuán)但不一定最大）為sta，若(sta & s[i]) == sta，則表示加入i點(diǎn)后仍能維護(hù)團(tuán)的性質(zhì)。然后將i點(diǎn)加入狀態(tài)再繼續(xù)搜索即可，sta | (1 << (i- 1))。記得位運(yùn)算要強(qiáng)制類型轉(zhuǎn)換！

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;//預(yù)處理成二進(jìn)制串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)));//位運(yùn)算記得要強(qiáng)制類型轉(zhuǎn)換前面的數(shù)} }

此代碼寫(xiě)法與前兩個(gè)感覺(jué)已經(jīng)有本質(zhì)區(qū)別了。

首先主程序中最開(kāi)始是由n~1開(kāi)始搜索的，每次搜索最開(kāi)始的i必須選，目的是可以用第一個(gè)很強(qiáng)的最優(yōu)性剪枝。

有些公式?jīng)]法放進(jìn)CSDN blog于是我就截圖了

code3效率是不錯(cuò)的（0.5s）

但由于最初我是從 n~1 枚舉的，因此有一個(gè)同樣很強(qiáng)的優(yōu)化用不上

但我提供下標(biāo)程給讀者思考吧

#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; }

總結(jié)

以上是生活随笔為你收集整理的最大团的求法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。