題目鏈接：http://poj.org/problem?id=2531

思路：由于N才20，可以dfs爆搞，枚舉所有的情況，復雜度為2^(n)。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 int map[22][22]; 8 int belong[22]; 9 int n,ans; 10 11 void dfs(int pos,int sum) 12 { 13 if(pos==n+1){ 14 ans=max(ans,sum); 15 return ; 16 } 17 belong[pos]=0; 18 int tmp=0; 19 for(int i=1;i<=pos;i++){ 20 if(belong[i]==1)tmp+=map[pos][i]; 21 } 22 dfs(pos+1,sum+tmp); 23 24 belong[pos]=1; 25 tmp=0; 26 for(int i=1;i<=pos;i++){ 27 if(belong[i]==0)tmp+=map[pos][i]; 28 } 29 dfs(pos+1,sum+tmp); 30 } 31 32 33 int main() 34 { 35 while(~scanf("%d",&n)){ 36 for(int i=1;i<=n;i++) 37 for(int j=1;j<=n;j++) 38 scanf("%d",&map[i][j]); 39 ans=0; 40 memset(belong,-1,sizeof(belong)); 41 dfs(1,0); 42 printf("%d\n",ans); 43 } 44 return 0; 45 } 46 47 48 49 View Code

?

轉載于:https://www.cnblogs.com/wally/p/3297301.html

總結

以上是生活随笔為你收集整理的poj 2531(dfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

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