題意：
? ? ? 給你一個無向圖，讓你找到這個圖里面的最大團是多少。
思路：
? ? ? 最大圖案是NP問題，直接暴力搜索，如果當前的這個點可以加入當前最大團，那么就選擇加入或者舍去，如果不能加入，直接舍去，還有一個剪枝就是當前的答案+后面剩余所有點 小于 當前的全局最大 的話直接return.


自己寫的跑了 4000+
#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優化后的 900+
#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) continue;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; }
? ?

? ? ??

總結

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

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