定義：?
? ? 最大團就是給你一個圖，讓你在這個圖里面找到一個最大的子圖，這個子圖必須是全圖，最大的子圖就是這個圖的最大團。


算法：
? ? ? 首先最大團是NP問題，沒有什么非常快的方法去解決，現在可以用搜索+剪枝去盡可能的快速處理最大團問題，其中一個很重要的剪枝就是如果當前集合的頂點數+剩下所有的點<當前全局的最優答案，那么直接return，不然搜下去也沒意義，我們要枚舉每一個團，找到最大的那個，對于當前點，如果滿足要求（和當前團所有點都有連邊）那么他可以加入團或者放棄，如果滿足要求，直接放棄，一直枚舉，更新最優就行了。
接著補充一下，經過做3585的那個二分最大團發現自己寫的模板各種超時，超時到蛋疼，最后學了下dp優化的，然后就過了，dp優化的理解是這樣的，對于dp優化首先我們要知道如果這樣的寫法


枚舉第一個點的時候for(int i = n - 1 ;i >= 1 ;i --)
DFS里面跑的時候for(int i = x + 1 ;i <= n ;i ++)
這樣就導致每次DFS是比上次增加了一個節點，對于當前點的本次搜索索要面臨的點都已經被枚舉過了，然后當前這個點加入如果是"有效"的,那么他肯定是之前的某一個團+1，如果當前的這個點要走的點+要走的那個點的之前最大團還是沒有當前全局答案大，那么就沒有必要遍歷了，直接就continue就行了。


//*******************************
最大團：圖G的頂點的子集D，若D中任意兩點相鄰，且含有的頂點數最大,則D為最大團。
? ? ? ? 因此若u,v在最大團中，則u,v必有邊相連
? ? ? ? 一個有N個頂點的最大團，邊數為N*（N-1）/2
求最大團是NP問題，常用的方法是DP優化+ DFS
?
與之相關的概念是最大獨立集：
獨立集是指圖的頂點集的一個子集,該子集的導出子圖不含邊。
一個圖中包含頂點數目最多的獨立集稱為最大獨立集。
所以最大獨立子集=圖的補圖的最大團
//***********************************


自己寫的一個模板（容易超時）


#include<stdio.h>


#define N 60


int map[N][N] ,n;
int now[N] ,Ans;


bool ok(int sum ,int to)
{
? ?for(int i = 1 ;i <= sum ;i ++)
? ?if(!map[now[i]][to]) return 0;
? ?return 1;
}


void DFS(int to ,int sum ,int node)
{
? ?if(Ans < sum) Ans = sum;
? ?if(sum + n - node < Ans) return;
? ?for(int i = to + 1 ;i <= n ;i ++)
? ?if(ok(sum ,i))?
? ?{
? ? ? now[sum + 1] = i;
? ? ? DFS(i ,sum + 1 ,node + 1);
? ?}
}


int main ()
{
? ?int i ,j;
? ?while(~scanf("%d" ,&n) && n)
? ?{
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? scanf("%d" ,&map[i][j]);
? ? ? Ans = 0;
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?now[1] = i;
? ? ? ? ?DFS(i ,1 ,1);
? ? ? }
? ? ? printf("%d\n" ,Ans);
? ?}
? ?return 0;
}


dp優化的（目前比較快的）
#include<stdio.h>


#define N 60


int map[N][N];
int dp[N] ,now[N];
int n ,Ans;


void DFS(int x ,int sum)
{
? ?if(sum > Ans) Ans = sum;
? ?
? ?int able = 0;
? ?int tnow[N];
? ?for(int i = x + 1 ;i <= n ;i ++)
? ?{
? ? ? tnow[i] = now[i];
? ? ? if(now[i]) able ++;
? ?}
? ?if(able + sum <= Ans) return;
? ?
? ?for(int i = x + 1 ;i <= n ;i ++)
? ?{
? ? ? if(!tnow[i]) continue;
? ? ? if(dp[i] + sum <= Ans) return;
? ? ? for(int j = x + 1 ;j <= n ;j ++)
? ? ? now[j] = tnow[j] & map[i][j];
? ? ? DFS(i ,sum + 1);
? ?}
}


int Max_Tuan()
{
? ?Ans = dp[n] = 1;
? ?for(int i = n - 1 ;i >= 1 ;i --)
? ?{
? ? ? for(int j = 1 ;j <= n ;j ++)
? ? ? now[j] = map[i][j];
? ? ? DFS(i ,1);
? ? ? dp[i] = Ans;
? ?}
? ?return Ans;
}


int main ()
{
? ?int i ,j;
? ?while(~scanf("%d" ,&n) && n)
? ?{
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? scanf("%d" ,&map[i][j]);
? ? ? printf("%d\n" ,Max_Tuan());
? ?}
? ?return 0;
}
? ?
? ?








? ? ??

總結

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

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